Modo efficiente di calcolare i punteggi di somiglianza delle stringhe quando la dimensione del campione è grande?

Question

Supponiamo che tu abbia un elenco di 10.000 indirizzi e-mail e desideri scoprire quali sono alcuni dei "vicini" più vicini " in questo elenco sono - definiti come indirizzi e-mail che sono sospettosamente vicini ad altri indirizzi e-mail nell'elenco.

Sono a conoscenza di come calcolare la Levenshtein distance tra due stringhe (grazie a questa domanda ), che mi darà un punteggio di quante operazioni sono necessarie per trasformare una stringa in un'altra.

Supponiamo che io definisca " sospettosamente vicino a un altro indirizzo email " come due stringhe con un punteggio di Levenshtein inferiore a N.

Esiste un modo più efficiente per trovare coppie di stringhe il cui punteggio è inferiore a questa soglia oltre a confrontare ogni possibile stringa con ogni altra possibile stringa nell'elenco? In altre parole, questo tipo di problema può essere risolto più rapidamente di O (n ^ 2) ?

Il punteggio Levenshtein è una cattiva scelta di algoritmi per questo problema?

Answer 1

Sì - puoi trovare tutte le stringhe entro una determinata distanza di una stringa nel tempo O (log n) usando un BK-Tree . Soluzioni alternative che comportano la generazione di ogni stringa con distanza n possono essere più veloci per una distanza di levenshtein pari a 1, ma la quantità di lavoro aumenta rapidamente fuori controllo per distanze più lunghe.

Answer 2

Puoi farlo con Levenshtein in O (kl) , dove k è la distanza massima e l è la stringa massima.

Fondamentalmente quando sai come calcolare Levenshtein di base, allora è facile capire che ogni risultato che è oltre k dalla diagonale principale deve essere maggiore di k . Quindi, se si calcola la diagonale principale con larghezza 2k + 1 sarà sufficiente.

Se hai 10000 indirizzi e-mail non avrai bisogno di un algoritmo più veloce. Il computer può calcolare con O (N ^ 2) abbastanza velocemente.

Levenshtein è abbastanza buono per questo tipo di problema.

Anche quello che potresti considerare è trasformare le e-mail con soundex prima del confronto. Probabilmente otterrai risultati migliori.

Answer 3

Questo problema è noto come clustering ed è parte di un problema maggiore di deduplicazione (in cui puoi decidere quale membro del cluster è " quello giusto " uno ), noto anche come unione-eliminazione .

Una volta ho letto alcuni articoli di ricerca esattamente su questo argomento (i nomi sono sotto) e sostanzialmente gli autori hanno usato una finestra scorrevole di dimensioni limitate su un elenco ordinato di stringhe. Confronterebbero soltanto (usando un modifica distanza algoritmo) N * N stringhe dentro la finestra, riducendo così la complessità computazionale. Se due stringhe sembravano simili, venivano combinate in un cluster (inserendo un record in una tabella di cluster separata).

Il primo passaggio nell'elenco è stato seguito da un secondo passaggio in cui le stringhe sono state invertite prima di essere ordinate. In questo modo le stringhe con teste diverse avevano un'altra possibilità di avvicinarsi abbastanza da essere valutate come parte della stessa finestra. In questo secondo passaggio, se una stringa sembrava abbastanza vicina a due (o più) stringhe nella finestra e tali stringhe facessero già parte dei loro cluster (trovati dal primo passaggio), i due cluster verrebbero quindi uniti (aggiornando la tabella dei cluster) e la stringa corrente verrebbe aggiunta al cluster appena unito. Questo approccio al clustering è noto come algoritmo union-find .

Quindi hanno migliorato l'algoritmo sostituendo la finestra con un elenco dei primi X prototipi sostanzialmente unici . Ogni nuova stringa verrebbe confrontata con ciascuno dei principali prototipi X. Se la stringa apparisse abbastanza vicina a uno dei prototipi, verrebbe quindi aggiunta al cluster del prototipo . Se nessuno dei prototipi avesse un aspetto abbastanza simile, la stringa diventerebbe un nuovo prototipo, spingendo il prototipo più vecchio fuori nell'elenco X in alto. (È stata utilizzata una logica euristica per decidere quale delle stringhe nel cluster del prototipo deve essere utilizzata come nuovo prototipo che rappresenta l'intero cluster). Ancora una volta, se la stringa apparisse simile a diversi prototipi, tutti i loro cluster verrebbero uniti.

Una volta ho implementato questo algoritmo per la deduplicazione dei record nome / indirizzo con dimensioni delle liste pari a circa 10-50 milioni di record e ha funzionato abbastanza velocemente (e ho trovato anche i duplicati).

Nel complesso per tali problemi, la parte più difficile ovviamente è trovare il giusto valore della soglia di somiglianza . L'idea è quella di catturare tutti i duplicati senza produrre troppi falsi positivi . I dati con caratteristiche diverse tendono a richiedere soglie diverse. La scelta di un algoritmo a distanza di modifica è anche importante poiché alcuni algoritmi sono migliori per gli errori OCR mentre altri sono migliori per gli errori di battitura e altri ancora per gli errori fonetici (come quando si ottiene un nome al telefono).

Una volta implementato l'algoritmo di clustering, un buon modo per testarlo è ottenere un elenco di campioni unici e mutare artificialmente ogni campione per produrne le variazioni, preservando il fatto che tutte le varianti hanno provengono dallo stesso genitore. Questo elenco viene quindi mischiato e inviato all'algoritmo. Il confronto tra il clustering originale e il clustering prodotto dall'algoritmo di deduplicazione ti darà il punteggio di efficienza .

Bibliografia:

Hernandez M. 1995, Il problema Unisci / Elimina per database di grandi dimensioni.

Monge A. 1997, Un algoritmo efficiente indipendente dal dominio per rilevare record di database approssimativamente duplicati.

Answer 4

Non penso che tu possa fare meglio di O (n ^ 2) ma puoi fare alcune piccole ottimizzazioni che potrebbero essere abbastanza veloci da rendere la tua applicazione utilizzabile:

• Puoi prima ordinare tutti gli indirizzi email per la parte dopo la @ e confrontare gli indirizzi solo dove è lo stesso
• Puoi interrompere il calcolo della distanza tra due indirizzi quando diventa maggiore di n

EDIT: in realtà puoi fare di meglio di O (n ^ 2), guarda la risposta di Nick Johnsons qui sotto.

Answer 5

10.000 indirizzi e-mail non suonano troppo. Per la ricerca di somiglianza in uno spazio più ampio puoi usare shingling e min-hashing . Questo algoritmo è un po 'più complicato da implementare, ma è molto più efficiente su un ampio spazio.

Answer 6

È possibile fare di meglio, a condizione di invertire il problema.

Suppongo che i tuoi 10.000 indirizzi siano piuttosto "corretti", altrimenti dovrai aggiungere un meccanismo di aggiornamento.

L'idea è di usare la distanza di Levenshtein, ma in modalità "inversa", in Python:

class Addresses:
  def __init__(self,addresses):
    self.rep = dict()
    self.rep[0] = self.generate_base(addresses)
      # simple dictionary which associate an address to itself

    self.rep[1] = self.generate_level(1)
    self.rep[2] = self.generate_level(2)
    # Until N

Il metodo generate_level genera tutte le possibili variazioni rispetto all'insieme precedente, meno le variazioni già esistenti a un livello precedente. Conserva "origine" come valore associato alla chiave.

Quindi, devi solo cercare la tua parola nei vari set:

  def getAddress(self, address):
    list = self.rep.keys()
    list.sort()
    for index in list:
      if address in self.rep[index]:
        return (index, self.rep[index][address]) # Tuple (distance, origin)
    return None

In questo modo, calcoli i vari set una volta (ci vogliono alcune volte ... ma poi puoi serializzarlo e tenerlo per sempre).

E quindi la ricerca è molto più efficiente di O (n ^ 2), anche se dargli esattamente è un po 'difficile poiché dipende dalla dimensione dei set che vengono generati.

Per riferimento, dai un'occhiata a: http://norvig.com/spell-correct.html

Answer 7

Supponiamo che tu abbia 3 stringhe:

1 - "abc" 2 - "bcd" 3 - "cde"

La distanza L tra 1 e amp; 2 è 2 (sottrai 'a', aggiungi 'd'). La distanza L tra 2 e amp; 3 è 2 (sottrai "b", aggiungi "e").

La tua domanda è se possiamo inferire una L Distanza tra 1 & amp; 3 usando i 2 confronti sopra. La risposta è no.

La distanza L tra 1 e amp; 3 è 3 (sostituisci ogni carattere), non è possibile dedurlo a causa dei punteggi dei primi 2 calcoli. I punteggi non rivelano se sono state eseguite cancellazioni, inserzioni o operazioni di sostituzione.

Quindi, direi che Levenshtein è una cattiva scelta per un ampio elenco.

Answer 8

Se stai davvero confrontando gli indirizzi e-mail, un modo ovvio per farlo sarebbe quello di combinare un algoritmo levenshtein con la mappatura del dominio. Mi vengono in mente delle volte in cui mi sono registrato per più volte utilizzando lo stesso dominio, ma variazioni nella parte del nome utente dell'indirizzo e-mail.