Быстрый нечеткий/приблизительный поиск в словаре строк в Ruby

Question

У меня есть словарь от 50K до 100K строк (может быть до 50 + символов), и я пытаюсь найти, является ли данная строка в словаре с некоторыми "edit «Допуск расстояния. (Например, Левенштейн). Перед выполнением поиска я отлично разбираюсь в какой-либо структуре данных.

Моя цель - запустить тысячи строк против этого словаря как можно быстрее и вернуть ближайшего соседа. Я был бы в порядке, просто получая логическое значение, которое скажет, присутствует ли данное значение в словаре или нет, если есть значительно более быстрый алгоритм для этого

Для этого я сначала попытался вычислить все расстояния Левенштейна и взять минимум и это было явно ужасно медленно. Так что я попытался реализовать Левенштейн TRIE на основе этой статьи http://stevehanov.ca/blog/index.php?id=114

Смотрите мою суть здесь для воспроизведения теста: https://gist.github.com/nicolasmeunier/7493947

Вот несколько тестов, которые я получил на моей машине:

Редактировать расстояние 0 (идеальный матч)

Benchmark.measure { 10.times { dictionary.search(random_word, 0) } } 
<Benchmark::Tms:0x007fa59bad8908 @label="", @real=0.010889, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.00999999999999801, @total=0.00999999999999801> 

* Изменить расстояние 2, она становится намного медленнее *

Benchmark.measure { 10.times { dictionary.search(random_word, 2) } } 
<Benchmark::Tms:0x007fa58c9ca778 @label="", @real=3.404604, @cstime=0.0, @cutime=0.0, @stime=0.020000000000000018, @utime=3.3900000000000006, @total=3.4100000000000006> 

И спускается оттуда и стать чрезвычайно медленным для редактирования расстояния больше, чем 2 (1+ секунду в среднем на тестируемой строки).

Я хотел бы знать, как/если бы я мог значительно ускорить это. Если существуют уже существующие решения в рубинах/драгоценных камнях, я также не хочу изобретать колесо ...

EDIT 1: В моем случае я ожидаю, что большинство строк, которые я сопоставляю со словарем NOT, быть там. Поэтому, если есть какой-либо алгоритм для быстрого удаления строки, это может реально помочь.

Спасибо, Николя

Answer 1

Я написал пару драгоценных камней, fuzzily и blurrily, которые делают триграмм на основе нечеткого соответствия. Учитывая ваш (низкий) объем данных. Легко будет интегрироваться и работать так же быстро, с помощью либо вы получите ответы в течение 5-10 мс на современном оборудовании.

Учитывая оба триграмм на основе (который индексируется), но не редактировать расстояния на основе (которая не является), то вы, вероятно, придется сделать это в два прохода:

• сначала спросить либо драгоценный камень для набора наилучших совпадений trigrams-wise
• затем сравните результаты с вашей входной строкой, используя Levenstein
• и верните мин для этой меры.

В Ruby (как вы просили), с использованием нечетко + Text gem, получение записей жгутов порога расстояние редактирования будет выглядеть следующим образом:

MyRecords.find_by_fuzzy_name(input_string).select { |result| 
    Text::Levenshtein.distance(input_string, result.name)] < my_distance_threshold 
} 

Это Performas горсть хорошо оптимизированных запросов базы данных и несколько

Предостережения:

• если «минимальное» расстояние редактирования вы ищете высокое, вы все равно будете дои нг много левенштейнов.
• Использование триграмм предполагает, что ваш текст ввода - латинский текст или близко к (в основном, европейские языки).
• , вероятно, есть краевые случаи, поскольку ничто не гарантирует, что «количество подходящих триграмм» является большим общим приближением к «расстоянию редактирования».

Answer 2

Около 15 лет назад я написал нечеткий поиск, который может найти N закрывает соседей. Это моя модификация алгоритма триграмм Уилбера и эта модификация под названием «Алгоритм Уилбера-Ховайко».

Основная идея: разбить строки на триграммы и найти максимальные оценки пересечения.

Например, у нас есть строка «hello world». Эта строка генерирует триграммы: hel ell llo "lo", "o_w", eand и так далее; Кроме того, для каждого слова создаются специальные триггеры префикса/суффикса, такие как $ he $ wo lo $ ld $.

После этого для каждого встроенного индекса триграмм, в каком члене он присутствует.

Итак, это список term_ID для каждой триграммы.

Когда пользователь вызывает некоторую строку - он также делится на триграммы и рассчитывает максимальный результат пересечения поисковых запросов и генерирует список N-размера.

Он работает быстро: я помню, на старом Sun/Солярисе, 256 Мб оперативной памяти, 200 МГц процессора, то поиск 100 ближайшего термина в словаре 5000000 терминов в 0.25s

Вы можете получить мой старый источник из: http://olegh.ftp.sh/wilbur-khovayko.tar.gz

UPDATE:

Я создал новый архив, где Makefile регулируется для современных Linux/BSD производства. Вы можете скачать новую версию здесь: http://olegh.ftp.sh/wilbur-khovayko.tgz

сделать директорию и извлечь архив здесь:

mkdir F2 
cd F2 
tar xvfz wilbur-khovayko.tgz 
make 

Go, чтобы проверить каталог, скопировать термин списка файлов (это фиксированное имя, termlist.txt), и индекс марки:

cd test/ 
cp /tmp/test/termlist.txt ./termlist.txt 
./crefdb.exe <termlist.txt 

В этом тесте я использовал ~ 380000 истекли доменные имена:

wc -l termlist.txt 
379430 termlist.txt 

Run findtest применения:

./findtest.exe 

boking <-- this is query -- word "booking" with misspeling 


0001:Query: [boking] 
    1: 287890 ( 3.863739) [bokintheusa.com,2009-11-20,$69] 
    2: 287906 ( 3.569148) [bookingseu.com,2009-11-20,$69] 
    3: 257170 ( 3.565942) [bokitko.com,2009-11-18,$69] 
    4: 302830 ( 3.413791) [bookingcenters.com,2009-11-21,$69] 
    5: 274658 ( 3.408325) [bookingsadept.com,2009-11-19,$69] 
    6: 100438 ( 3.379371) [bookingresorts.com,2009-11-09,$69] 
    7: 203401 ( 3.363858) [bookinginternet.com,2009-11-15,$69] 
    8: 221222 ( 3.361689) [bobokiosk.com,2009-11-16,$69] 
    . . . . 
97: 29035 ( 2.169753) [buccupbooking.com,2009-11-05,$69] 
98: 185692 ( 2.169047) [box-hosting.net,2009-11-14,$69] 
99: 345394 ( 2.168371) [birminghamcookinglessons.com,2009-11-25,$69] 
100: 150134 ( 2.167372) [bowlingbrain.com,2009-11-12,$69] 

Answer 3

Здесь представлена ​​необработанная Trie-подобная реализация. Это полностью не оптимизировано, просто доказательство концепции. Чистая реализация Ruby.

Чтобы проверить это, я взял 100_000 слова здесь http://www.infochimps.com/datasets/word-list-100000-official-crossword-words-excel-readable/downloads/195488

здесь является сутью для него https://gist.github.com/fl00r/7542994

class TrieDict 
    attr_reader :dict 

    def initialize 
    @dict = {} 
    end 

    def put(str) 
    d = nil 
    str.chars.each do |c| 
     d && (d = (d[1][c] ||= [nil, {}])) || d = (@dict[c] ||= [nil, {}]) 
    end 
    d[0] = true 
    end 

    def fetch(prefix, fuzzy = 0) 
    storage = [] 
    str = "" 
    error = 0 
    recur_fetch(prefix, fuzzy, @dict, storage, str, error) 
    storage 
    end 

    def recur_fetch(prefix, fuzzy, dict, storage, str, error) 
    dict.each do |k, vals| 
     e = error 
     if prefix[0] != k 
     e += 1 
     next if e > fuzzy 
     end 
     s = str + k 
     storage << s if vals[0] && (prefix.size - 1) <= (fuzzy - e) 
     recur_fetch(prefix[1..-1] || "", fuzzy, vals[1], storage, s, e) 
    end 
    end 
end 

def bench 
    t = Time.now.to_f 
    res = nil 
    10.times{ res = yield } 
    e = Time.now.to_f - t 
    puts "Elapsed for 10 times: #{e}" 
    puts "Result: #{res}" 
end 

trie = TrieDict.new 
File.read("/home/petr/code/tmp/words.txt").each_line do |word| 
    trie.put(word.strip) 
end; :ok 
# Elapsed for 10 times: 0.0006465911865234375 
# Result: ["hello"] 
bench{ trie.fetch "hello", 1 } 
# Elapsed for 10 times: 0.013643741607666016 
# Result: ["cello", "hallo", "helio", "hell", "hello", "hellos", "hells", "hillo", "hollo", "hullo"] 
bench{ trie.fetch "hello", 2 } 
# Elapsed for 10 times: 0.08267641067504883 
# Result: ["bell", "belle", "bellow", "bells", "belly", "cell", "cella", "celli", "cello", "cellos", "cells", "dell", "dells", "delly", "fell", "fella", "felloe", "fellow", "fells", "felly", "hall", "hallo", "halloa", "halloo", "hallos", "hallot", "hallow", "halls", "heal", "heals", "heel", "heels", "heil", "heils", "held", "helio", "helios", "helix", "hell", "helled", "heller", "hello", "helloed", "helloes", "hellos", "hells", "helm", "helms", "helot", "help", "helps", "helve", "herl", "herls", "hill", "hillo", "hilloa", "hillos", "hills", "hilly", "holla", "hollo", "holloa", "holloo", "hollos", "hollow", "holly", "hull", "hullo", "hulloa", "hullos", "hulls", "jell", "jells", "jelly", "mell", "mellow", "mells", "sell", "selle", "sells", "tell", "tells", "telly", "well", "wells", "yell", "yellow", "yells"] 
bench{ trie.fetch "engineer", 2 } 
# Elapsed for 10 times: 0.04654884338378906 
# Result: ["engender", "engine", "engined", "engineer", "engineered", "engineers", "enginery", "engines"] 
bench{ trie.fetch "engeneer", 1 } 
# Elapsed for 10 times: 0.005484580993652344 
# Result: ["engender", "engineer"] 

Answer 4

Если вы готовы принять участие с Machine Learning подходы, то этот документ, Geoff Хинтон будет хорошей отправной точкой

http://www.cs.toronto.edu/~hinton/absps/sh.pdf

Эти подходы используются в таких местах, как Google и т. Д.

По существу, вы кластерируете словарные строки на основе подобия. Когда приходит строка запроса, вместо вычисления расстояния редактирования по всему набору данных вы просто сравниваете кластер, тем самым значительно сокращая время запроса.

PS Я сделал немного прибегая к помощи, нашел реализацию рубина другого подобного подхода называется Locality Sensitive Hashing здесь https://github.com/bbcrd/ruby-lsh