5
Diciamo che ho qualche miliardo di righe di testo e qualche milione di "parole chiave". Il compito è quello di passare attraverso queste linee e vedere quale riga contiene quali parole chiave. In altre parole, data una mappa di (K1 -> V1) e (K2 -> V2), creare una mappa di (K2 -> K1) dove K1=lineID, V1=text, K2=keywordID e V2=keyword. Si noti inoltre che:Modo più efficiente/libreria per rilevare parole chiave predefinite in miliardi di righe?
- tutto il testo/parole chiave sono l'inglese
- Testo (V1) possono contenere errori di ortografia.
- La maggior parte delle parole chiave (V2) sono singole parole, ma alcune parole chiave può essere costituito da più di una parola inglese (ad esempio, "asciugamano pulito")
Finora la mia idea iniziale per risolvere questo è il seguente:
1) Chop up all my keywords into single words and
create a large set of single words (K3)
2) Construct a BK-Tree out of these chopped up keywords,
using Levenshtein distance
3) For each line of data (V1),
3.1) Chop up the text (V1) into words
3.2) For each said word,
3.2.1) Retrieve words (K3) from the BK-Tree that
are close enough to said word
3.3) Since at this point we still have false positives,
(e.g. we would have matched "clean" from "clean water" against
keyword "clean towel"), we check all possible combination
using a trie of keyword (V2) to filter such false
positives out. We construct this trie so that at the
end of an successful match, the keywordID (K2) can be retrieved.
3.4) Return the correct set of keywordID (K2) for this line (V1)!
4) Profit!
Le mie domande
- È questo un buon approccio? L'efficienza è molto importante - ci sono dei modi migliori? Qualcosa da migliorare?
- Esistono librerie che potrei usare? Preferibilmente qualcosa che funzionerebbe bene con Java.
Grazie in anticipo!
Vedi http://stackoverflow.com/questions/4945829/improving-performance-of-fuzzy-string-matching-against -un dizionario –