Быстрый поиск по индексу ngram - PullRequest
Новая
       16

Быстрый поиск по индексу ngram

0 голосов
/ 27 августа 2018

Я пишу программу на python, которая находит наиболее похожие слова по заданному входному слову (используя алгоритм редактирования расстояния). Это должно работать так: 

input = "tree"

output = [ "free", "trek", "trie" ]

Пока я извлек все нграммы из лексикона и связал их со словами, из которых они были извлечены. У меня есть словарь, где ключи - это нграммы, а значения - списки связанных слов, например:

"маг": ["магия", "журнал", "магнит", "магистрат", "паломничество"]

Когда у меня есть входное слово, я извлекаю из него нграммы и перебираю ключи в словаре, чтобы найти их и извлечь связанные списки со словами. В этих списках я использую расстояние редактирования, чтобы получить слова, которые мне нужны. Это хорошо работает, но занимает много времени. Иногда это прибывает в 8/10 секунд только для одного слова. Как мне ускорить процесс? Я на самом деле хочу концептуальное решение. Я использовал этот подход «индекс ngram», потому что использование расстояния редактирования для каждого слова в лексиконе было намного медленнее. Теперь я хочу что-то быстрее, чем мой текущий метод 

def searchIndex(myString, n, index):
ngs = toNgrams(myString)
found=[]
ngIndex = NGram(index)
ngNgrams = NGram(ngs)

a = timer()
commonNgrams = ngIndex.intersection(ngNgrams)
for i in commonNgrams:
    for k in index[i]:
        if ed(myString, k) < 2 and k not in found:
            found.append(k)
b = timer()
time = b-a
return found, time
...