Ricerca sfocata per una sottostringa senza token

Risponderò alla mia stessa domanda con questi collegamenti:

link

link

Il secondo link contiene la seguente funzione:

def fuzzy_substring(needle, haystack):
    """Calculates the fuzzy match of needle in haystack,
    using a modified version of the Levenshtein distance
    algorithm.
    The function is modified from the levenshtein function
    in the bktree module by Adam Hupp"""

    m, n = len(needle), len(haystack)

    # base cases
    if m == 1:
        return not needle in haystack
    if not n:
        return m

    row1 = [0] * (n+1)
    for i in range(0,m):
        row2 = [i+1]
        for j in range(0,n):
            cost = ( needle[i] != haystack[j] )

            row2.append( min(row1[j+1]+1, # deletion
                               row2[j]+1, #insertion
                               row1[j]+cost) #substitution
                           )
        row1 = row2
    return min(row1)

lines = """Lorem ipsum dolor sit amet, (tag) consectetur adipiscing elit.
Phasellus congue nisi vel lorem dignissim tristique. (tag)
Etiam vulputate lacus nec velit lobortis ut adipiscing mauris condimentum. (tag )
Vestibulum quis nulla id nisi ultricies placerat. (teg)
In tempus vulputate ante, quis suscipit nunc euismod in. (teg )
Phasellus iaculis diam in felis pellentesque tristique. (ta g)
(tag Praesent vestibulum sollicitudin velit, non mollis lacus scelerisque in.
Nunc ac erat enim, at lobortis libero. (interesting)""".split('\n')

for line in lines:
    print fuzzy_substring('(tag)', line), line

L'output è:

0 Lorem ipsum dolor sit amet, (tag) consectetur adipiscing elit.
0 Phasellus congue nisi vel lorem dignissim tristique. (tag)
1 Etiam vulputate lacus nec velit lobortis ut adipiscing mauris condimentum. (tag )
1 Vestibulum quis nulla id nisi ultricies placerat. (teg)
2 In tempus vulputate ante, quis suscipit nunc euismod in. (teg )
1 Phasellus iaculis diam in felis pellentesque tristique. (ta g)
1 (tag Praesent vestibulum sollicitudin velit, non mollis lacus scelerisque in.
3 Nunc ac erat enim, at lobortis libero. (interesting)

Ho fatto qualcosa di simile a questo un po 'di tempo fa, solo che stavo abbinando le parole a una parola ricercata. Questo potrebbe non aiutarti, ma potrebbe darti un'idea.

Essenzialmente, quello che ho fatto è stato qualcosa del genere:

Per ogni parola nel mio intervallo e ho fatto qualcosa di simile a un diff . Ho considerato la lettera nella stringa e la sua posizione. Per le lettere corrette ho dato un punto, per la corretta posizione nella stringa ho dato un punto. Per il cattivo e il posizionamento vorrei rimuovere un punto, e per le lettere mancanti vorrei rimuovere un punto. (È difficile da ricordare, perché non ho più accesso alla sorgente, ma penso di aver anche basato il punto di posizionamento sulla distanza dalla posizione prevista).

Dopo aver risposto al "punteggio" di questa parola, mi normalizzerei. Avevo una soglia arbitraria (trovata per tentativi ed errori, ma poteva essere guidata dal feedback) che ho usato per determinare se fosse abbastanza vicina.

Quindi tutte le parole che erano al di sopra della soglia sono state restituite all'utente in ordine decrescente.

IIRC, non è stato particolarmente efficace per le parole brevi, ma nel complesso è stato abbastanza efficace per la sua implementazione (ricerca su un dominio specifico).

Spero che ti aiuti in una direzione produttiva.