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

Question

Добрый день,

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

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

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

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

Answer 1

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

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

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

, мы генерируем параметрические описания как упакованные длинные [] массивытак что это не сделает наш 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

Answer 2

Я перенес соответствующий 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).

Answer 3

Вот, пожалуйста.

/// <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];
}

Answer 4

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

Если вам нужно решение, способное создавать такие таблицы с нуля в памяти, вы можете взглянуть на LevenshteinAutomaton . Он написан на Java, но он хорошо структурирован, прост в использовании и широко комментируется, поэтому его проще переносить на C #, чем в текущей реализации Lucene. Также поддерживается moi .

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

Answer 5

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

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

Answer 6

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

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