La corrispondenza del nome parziale in milioni di record

Question

La corrispondenza del nome parziale in milioni di record

#1 da (6 voti)

10

Abbiamo sviluppato un'applicazione basata sul Web per la corrispondenza dei nomi. Funziona suddividendo i nomi in parti e il valore Soundex di ogni parte è memorizzato in un database. La metrica di distanza Levenshtein viene utilizzata per applicare la corrispondenza percentuale del suono e l'ortografia di un determinato nome.

In fase di runtime, cariciamo tutti i record in memoria e applichiamo la distanza Levenshtein a tutti i valori Soundex e all'ortografia di tutte le parti di tutti i nomi.

All'inizio funzionava bene perché c'erano al massimo 20.000 nomi, ma ora uno dei nostri clienti ha 30 milioni di nomi. Il caricamento di questo elenco enorme in memoria per ogni richiesta e l'applicazione di questo tipo di corrispondenza è un approccio patetico, che utilizza molta memoria e tempi di esecuzione.

Stiamo cercando suggerimenti per la ricerca di un database di 30 milioni di dischi o più nel prossimo futuro con la corrispondenza percentuale di suoni e ortografia.

Funzionalità di base

L'utente finale inserisce il nome da abbinare e la percentuale minima. Dovremmo mostrare tutti quei nomi nel database per cui qualsiasi parte del nome corrisponde a qualsiasi parte del nome dato fino alla percentuale data. Non è necessario che il nome completo sia abbinato, qualsiasi parte se la corrispondenza fino alla percentuale è un successo. Ad esempio.

Given Name: Helen Hunt
Name in DB: Holly Hunter

Entrambe le parti di entrambi i nomi non corrispondono esattamente ma in una certa misura, assumiamo l'80%, quindi se l'utente inserisce l'80%, il nome in DB deve essere mostrato come nome corrispondente.

asp.net sql-server search oracle big-data

posta bjan 10.08.2016 - 20:08

fonte

1 risposta

Leggi altre domande sui tag asp.net sql-server search oracle big-data

Qual è un buon modo per rappresentare una relazione molti-a-molti tra due classi? È una buona idea fare TDD su componenti di basso livello?

score 6 · Accepted Answer

Senza conoscere tutti i dettagli di ciò che ti serve, probabilmente vuoi fare una delle seguenti azioni:

Utilizza uno strumento di ricerca esistente, come Sfinge o Lucene
Esegui corrispondenza approssimativa n-gram

Non so bene cosa comporta l'installazione e la configurazione della sfinge; ma, ho l'impressione che tu possa indirizzarlo a un database, dirgli quali campi indicizzare, come ponderare i risultati e ti darà un elenco ordinato di record corrispondenti.

Per gli elementi critici per l'utente o per la missione, utilizza uno strumento di ricerca esistente.

Se ti senti semplicemente accademico ... Gioca con ngrams:

Una tabella di ricerca di ngram può servire come set iniziale di potenziali corrispondenze e puoi utilizzare le distanze di Levenshtein per ridurre e ordinare i risultati.

Supponendo che tu voglia cercare people , potresti fare qualcosa del tipo:

_ people _________
personId: int
name: varchar
soundex_name: varchar

_ people_ngrams __
personId: int
ngramId: int

_ ngrams _________
ngramId: int
ngram: char(3)
count: int

Puoi periodicamente ricostruire i tuoi ngrams o costruirli al volo. Ad ogni modo, un semplice algoritmo di ricerca ingenuo può apparire come questo:

search_ngrams = ngrammify(soundex(search_string));

notable_ngrams = select top 10 *
  from ngrams
  where ngram in (search_ngrams)
  order by count asc;

possible_matches = select top 1000 distinct people.*
  from people_ngrams, people
  where ngramId in (notable_ngrams);

best_matches = top 100 possible_matches
  ordered by Levenshtein_distance(match, soundex(search_string));

Usando qualcosa di abbastanza simile a questo (ma con un po 'più ngram "popolarità" di sintonizzazione, blacklist, whitelist, ecc.), ho visto questo tipo di algoritmo fondere in modo univoco record tra set di dati alla rinfusa, oltre a facilitare le utility di ricerca fuzzy personalizzate e gli sforzi di de-duplicazione dei record in corso.

Ora, nel mio caso, non corrispondevo a milioni di record, stavo cercando di selezionare le migliori combinazioni possibili tra due set di dati dell'ordine di centinaia di migliaia di record ciascuno. E volevamo che funzionasse abbastanza velocemente, in pochi minuti. (Veloce, cosa sono 100.000 * 100.000?) E, abbiamo avuto successo.

Quindi, con la giusta sintonia, questo genere di cose può essere scattante ed efficace. Alla fine siamo stati in grado di produrre un insieme unito su una macchina dual-core umile e datata in pochi minuti, con fusioni "discutibili" automaticamente contrassegnate per revisione manuale. Ma ci è voluto un sacco di tempo per trovare la popolarità ngram / pertinenza sweet-spot, e le giuste soglie di distanza tra stringhe e blacklist e whitelist ... ecc.

CHE HA DATO , puoi davvero essere risucchiato da un buco a lavorare su questa roba. Per qualsiasi elemento di produzione di livello reale, dovresti generalmente utilizzare uno strumento consolidato già reso e ottimizzato per questo tipo di ricerca .

Come Sfinge o Lucene .