Быстрый нечеткий / приблизительный поиск по словарю строк в 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) } }
<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+ секунды в среднем на тестируемую строку).

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

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

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

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

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