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

Question

Знаете ли вы какую-либо библиотеку .NET для текстовых алгоритмов ??
Особенно меня интересуют совпадения строк и алгоритмы полнотекстового поиска, такие как

• Битовый алгоритм
• Расстояние Левенштейна
• Расстояние Дамерау – Левенштейна

Я знаю, что тот, который я упомянул, довольно прост для кодирования, но существуют сотни текстовых алгоритмов, я не хочу кодировать их все самостоятельно.
Если нет такой известной библиотеки .NET, вы можете упомянуть C, C ++ библиотеку, оболочка для кодирования будет проще, чем кодирование с нуля.

Answer 1

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

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

ОБНОВЛЕНИЕ:

Небольшое копание нашло реализацию Левенштейна в C # на CodeProject.

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

UPDATE # 2:

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

Расстояние Левенштейна в C # (любезно предоставлено 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)];

    }

Answer 2

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

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

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

Answer 3

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

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

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

Answer 4

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

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

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

Лицензия GPLv2.

Answer 5

вот то, что я реализовал для расстояния Левенштейна / Дамерау – Левенштейна:

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

Answer 6

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