Левенштейн ДФА в.NET

Добрый день,

Кто-нибудь знает о "готовой" реализации реализации DFA Левенштейна (детерминированные конечные автоматы) в.NET (или легко переносимой на него)? У меня очень большой словарь с более чем 160000 различными словами, и я хочу, чтобы, учитывая начальное слово w, все эффективные слова на расстоянии Левенштейна были найдены не более 2 от w.

Конечно, наличие функции, которая вычисляет все возможные правки на расстоянии редактирования одного из заданных слов, и повторное применение к каждому из этих правок решает проблему (и довольно простым способом). Проблема в эффективности - учитывая 7-буквенное слово, это может занять более 1 секунды, и мне нужно что-то гораздо более эффективное - если это возможно, как, например, с DFA Левенштейна, решение, которое принимает O (| ш |) шаги.

Редактировать: Я знаю, что я могу построить свой собственный подход к проблеме с небольшим изучением, но в настоящее время я не могу позволить себе читать статьи Шульца и Михова на 60 страницах.

Большое спасибо.

Источник

6 ответов

Решение

Мы реализовали это для Apache Lucene Java, возможно, вы могли бы преобразовать его в C# и сэкономить время.

основной класс здесь: это всего лишь конструктор, который извлекает DFA Левенштейна из строки, используя алгоритм Шульца и Михова.

http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/LevenshteinAutomata.java

параметрические описания (предварительно вычисленные таблицы) для Lev1 и Lev2 находятся здесь: http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Lev1ParametricDescription.java

http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/Lev2ParametricDescription.java

вы можете заметить, что они генерируются на компьютере, мы сгенерировали их с помощью этого скрипта, используя замечательную реализацию Жан-Филиппа Барретта (python) http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/createLevAutomata.py

мы генерируем параметрические описания в виде упакованных массивов long[], чтобы наш файл JAR не был слишком большим.

просто измените toAutomaton(int n), чтобы он соответствовал вашим потребностям / пакету DFA. в нашем случае мы используем модифицированную форму пакета brics automaton, где переходы представлены в виде диапазонов кодовых точек Юникода.

Эффективные модульные тесты трудны для такого рода вещей, но вот что мы придумали... это кажется тщательным и даже нашло ошибку (которая была немедленно исправлена ​​автором!) в реализации moman.

http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/test/org/apache/lucene/util/automaton/TestLevenshteinAutomata.java

Источник

Ну вот.

/// <summary>
/// Levenshtein Distance Calculator
/// </summary>
public static int DistanceFrom(this string s, string t)
{
    int n = s.Length;
    int m = t.Length;
    int[,] d = new int[n + 1, m + 1];

    // Step 1
    if (n == 0)
        return m;

    if (m == 0)
        return n;

    // Step 2
    for(int i = 0; i <= n; d[i, 0] = i++) ;
    for(int j = 0; j <= m; d[0, j] = j++) ;

    // Step 3
    for (int i = 1; i <= n; i++)
    {
        //Step 4
        for (int j = 1; j <= m; j++)
        {
            // Step 5
            int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

            // Step 6
            d[i, j] = Math.Min(
                Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                d[i - 1, j - 1] + cost);
        }
    }
    // Step 7
    return d[n, m];
}
Источник

Я перенес соответствующий Java-код Lucene, предложенный Робертом Мьюиром, на C#. Что касается вопроса и "из коробки": это работа в процессе, но код, кажется, работает и, вероятно, может быть оптимизирован - дальше, хотя он действительно работает очень хорошо.

Вы можете найти его здесь: https://github.com/mjvh80/LevenshteinDFA/.

ОБНОВЛЕНИЕ: Похоже, что Lucene.NET на самом деле не мертва (пока?), И я заметил, что теперь у них также есть портированная версия этого кода. Поэтому я бы порекомендовал поискать там ( https://github.com/apache/lucenenet/blob/master/src/Lucene.Net.Core/Util/Automaton/LevenshteinAutomata.cs) реализацию этого.

¹ код требует больше тестов
² потому что это java, портированный на C#, возможно, и потому что я написал наивные замены некоторых классов (например, bitset).

Источник

Я понимаю, вы хотите найти близкие совпадения в большом словаре. Вот как я это делаю. ссылка на сайт.

Из того, что я могу понять о DFA, я не могу понять, насколько лучше, или даже совсем иначе, под кожей. НФА могут быть быстрее, но это потому, что они не существуют. Может я не прав.

Источник

У Ника Джонсона есть очень подробное сообщение в блоге о создании автомата Левенштейна в Python, и код здесь. Это хорошее чтение, и я использовал слегка измененную версию кода, которую я нашел эффективной.

Ответ Майка Данлавей тоже хорош. Интересно, что в этом случае наиболее эффективно: поиск по три или DFA Левенштейна?

Источник

Хотелось бы отметить, что на данный момент реализации автомата Левенштейна в Lucene и Lucene.Net используют файлы, содержащие таблицы параметрических состояний (таблицы абстрактных состояний, которые описывают конкретные состояния в автомате), созданные с использованием Moman.

Если вам нужно решение, способное создавать такие таблицы с нуля в памяти, вы можете взглянуть на https://github.com/klawson88/Levenshtein Automaton. Он написан на Java, но он хорошо структурирован, прост в использовании и широко комментируется, поэтому его легче переносить на C#, чем в текущей реализации Lucene. Это также поддерживается моим.

* Забавный факт: я отправил Levenshtein Automaton как замену или как ссылку для замены на текущую реализацию Levenshthein Automaton в Lucene... 3 года назад.

Источник
Другие вопросы по тегам