. Biblioteca de .NET para algoritmos de texto?

Question

¿Conoces alguna biblioteca .NET para algoritmos de texto?
Sobre todo estoy interesado en partido de cuerdas, y los algoritmos de búsqueda de texto completo como

• algoritmo BITAP
• distancia Levenshtein
• Damerau-distancia Levenshtein

sé el que yo he mencionado que son bastante simples de codificar, pero hay cientos de algoritmos de texto, no quiero codificarlos solo.
Si no se conoce dicha biblioteca .NET, puede mencionar la biblioteca C, C++, la envoltura de codificación será más fácil que la codificación desde cero.

Answer 1

he conseguido encontrar implementaciones de la mayoría de los algoritmos que necesito que utilizan combinación de buscar en Wikipedia + Google Code.

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

Aunque es extraño que nadie ha creado el proyecto sobre este tema, donde las personas interesadas pueden colaborar en esto.

Answer 2

Si está haciendo una coincidencia de cadenas, vale la pena echarle un vistazo a Lucene.Net.

Sin embargo, sé que esto no es exactamente lo que buscas, y aunque puedes encontrar la mayoría de esos algoritmos en algún formulario C#, no conozco ninguna biblioteca que los incorpore (tendí a mantener un par de estos en mi biblioteca personal).

Fuera de interés, ¿por qué necesitaría más de uno de estos algoritmos de coincidencia total con un par de parámetros de umbral?

Answer 3

Puede que esté interesado en echar un vistazo a la biblioteca google-diff-match-patch en Google Code. Tienen una implementación del algoritmo diff de Myer y afirma implementar también un algoritmo Bitap "en el corazón".

Tiene la fuente C# que está buscando, así como las implementaciones en Java, C++, Lua & Python. Aunque no tengo la mejor comprensión de cómo usar Bitap en la práctica (hay demos en el proyecto de Google Code), creo que estarás más interesado en las funciones de coincidencia que comienzan alrededor de la línea 1476 del current version.

ACTUALIZACIÓN:

Un poco de investigación encontró una implementación de Levenshtein in C# en CodeProject.

Además, this C# class file contiene una implementación de Levenshtein en SourceForge. La implementación es parte del proyecto Corsis (también conocido como Tenka Text). El autor afirma que el método YetiLevenshtein (alrededor de la línea 741) es de 2 veces a 10 veces más rápido que la implementación utilizada en la versión CodeProject del algoritmo mencionado anteriormente.

ACTUALIZACIÓN # 2:

acabo de descubrir el wikilibro Algorithm implementation con ella es C# versión de Levenshtein Distancia y tuvo que incluirlo porque se ve bastante simple y al punto. Este wikibook parece una gran referencia para tener a mano en general.

Levenshtein Distance in C# (cortesía de Wikilibros)

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 4

Encontré y usé the following .NET library implementando Aho-Corasick text mathcing de Tom Petricek en un problema que tuve. Funciono muy bien para mi.

Answer 5

aquí es uno que he implementado para Levenshtein/Damerau-Levenshtein distancia:

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

puedo sugerir SimMetrics biblioteca, que tiene muchos algoritmos diferentes para la coincidencia de cadenas. Disponible también en NuGet.

Breve descripción:

SimMetrics es una biblioteca Metric Similitud, por ejemplo desde la distancia de edición (Levenshtein, Gotoh, Jaro, etc.) a otras métricas (por ejemplo, Soundex, Chapman).

licencia GPLv2.