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

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

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

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

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

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

Изменить расстояние 0 (идеальное совпадение) *

Benchmark.measure { 10.times { dictionary.search(random_word, 0) } }
 

Отредактируйте расстояние 2, оно станет намного медленнее *

Benchmark.measure { 10.times { dictionary.search(random_word, 2) } }

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

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

РЕДАКТИРОВАТЬ 1: В моем случае, я ожидаю, что большинство строк, которые я сопоставляю со словарем, НЕ будет там. Так что, если есть какой-либо алгоритм для быстрого сброса строки, это действительно может помочь.

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

Ответы на вопрос(4)

Ваш ответ на вопрос