Библиотека .NET для текстовых алгоритмов?

Ответ 1

Мне удалось найти реализации большинства алгоритмов, которые мне нужны, используя комбинацию поиска WikiPedia + Google Code.

http://en.wikipedia.org/wiki/Category:Algorithms_on_strings
http://www.google.com/codesearch

Хотя странно, что никто не создал проект по этому вопросу, где заинтересованные люди могли бы сотрудничать в этом.

Ответ 2

Вам может быть интересно проверить библиотеку google-diff-match-patch в Google Code. У них есть реализация алгоритма Myer diff, и он утверждает, что также реализует алгоритм Bitap "в основе".

Он имеет источник С#, который вы ищете, а также реализации в Java, С++, Lua и Python. Хотя у меня нет лучшего понимания того, как использовать Bitap на практике (есть демонстрации в проекте Google Code). Я думаю, вас больше всего интересуют функции соответствия, начиная с строки 1476 текущая версия.

ОБНОВЛЕНИЕ:

Немного копания обнаружила реализацию Levenshtein в С# в CodeProject.

Кроме того, этот файл класса С# содержит реализацию Levenshtein на SourceForge. Реализация является частью проекта Corsis (aka Tenka Text). Автор утверждает, что метод YetiLevenshtein (вокруг строки 741) на 2-10 раз быстрее, чем реализация, используемая в версии CodeProject алгоритма, упомянутого выше.

ОБНОВЛЕНИЕ # 2:

Я только что открыл wikibook реализация алгоритма с его версией на С# версии Levenshtein Distance и должен был включить его, потому что он выглядит довольно прямолинейно и точно, Этот wikibook выглядит как отличная рекомендация держать под рукой в ​​целом.

Расстояние Левенштейна в С# (любезно предоставлено Wikibooks)

    private Int32 levenshtein(String a, String b)
    {

        if (string.IsNullOrEmpty(a))
        {
            if (!string.IsNullOrEmpty(b))
            {
                return b.Length;
            }
            return 0;
        }

        if (string.IsNullOrEmpty(b))
        {
            if (!string.IsNullOrEmpty(a))
            {
                return a.Length;
            }
            return 0;
        }

        Int32 cost;
        Int32[,] d = new int[a.Length + 1, b.Length + 1];
        Int32 min1;
        Int32 min2;
        Int32 min3;

        for (Int32 i = 0; i <= d.GetUpperBound(0); i += 1)
        {
            d[i, 0] = i;
        }

        for (Int32 i = 0; i <= d.GetUpperBound(1); i += 1)
        {
            d[0, i] = i;
        }

        for (Int32 i = 1; i <= d.GetUpperBound(0); i += 1)
        {
            for (Int32 j = 1; j <= d.GetUpperBound(1); j += 1)
            {
                cost = Convert.ToInt32(!(a[i-1] == b[j - 1]));

                min1 = d[i - 1, j] + 1;
                min2 = d[i, j - 1] + 1;
                min3 = d[i - 1, j - 1] + cost;
                d[i, j] = Math.Min(Math.Min(min1, min2), min3);
            }
        }

        return d[d.GetUpperBound(0), d.GetUpperBound(1)];

    }

Ответ 3

Если вы выполняете сопоставление строк, Lucene.Net стоит посмотреть.

Тем не менее, я знаю, что это не совсем то, что вам нужно, и хотя вы можете найти большинство этих алгоритмов в какой-то форме С#, я не знаю, какая библиотека их включает (я имел тенденцию держать пару таких в моей личной библиотеке).

Из интереса, почему вам понадобится больше одного из этих алгоритмов полного соответствия с несколькими пороговыми параметрами?

Ответ 4

вот один, который я применил для расстояния Левенштейн/Дамерау-Левенштейн:

    public static int GetDistance(string left, string right, bool isDamerauDistanceApplied)
    {
        if (left.Length == 0) return right.Length;
        if (right.Length == 0) return left.Length;

        var lenLeft = left.Length;
        var lenRight = right.Length;

        var matrix = new int[lenLeft + 1, lenRight + 1];

        for (var i = 0; i <= lenLeft; i++)
            matrix[i, 0] = i;

        for (var i = 0; i <= lenRight; i++)
            matrix[0, i] = i;

        for (var i = 1; i <= lenLeft; i++)
        {
            for (var j = 1; j <= lenRight; j++)
            {
                var cost = (left[i - 1] == right[j - 1]) ? 0 : 1;

                matrix[i, j] = Math.Min(Math.Min(matrix[i - 1, j] + 1, matrix[i, j - 1] + 1), matrix[i - 1, j - 1] + cost);

                if (isDamerauDistanceApplied)
                {
                    // Fixed for string base 0 index.
                    if (i > 1 && j > 1 && left[i - 1] == right[j - 2] && left[i - 2] == right[j - 1])
                    {
                        matrix[i, j] = Math.Min(matrix[i, j], matrix[i - 2, j - 2] + cost);
                    }
                }
            }
        }

        return matrix[lenLeft, lenRight];
    }

Ответ 5

Я предлагаю SimMetrics библиотеку, у нее есть много разных алгоритмов для сопоставления строк. Доступно также на NuGet.

Краткое описание:

SimMetrics - это метрическая библиотека сходства, например. от расстояния редактирования (Левенштейн, Готох, Джаро и т.д.) К другим метрикам (например, Soundex, Чапмен).

Лицензия GPLv2.

Ответ 6

Я нашел и использовал следующую библиотеку .NET, в которой была реализована математическая математика Aho-Corasick от Тома Петричека по проблеме, которую я имел. Это отлично поработало для меня.