Langage C#
  1. Langage C#
  3. Bibliothèque .NET pour les algorithmes de texte?
Intereting Posts
Comment puis-je afficher la sum de dans une colonne datagridview? Types booléens LINQ et un ordre de sorting naturel Aide Linq – La trace SQL renvoie le résultat, mais datacontext renvoie null Les structs sont-ils ‘pass-by-value’? Est-il possible de générer des documents Word de manière dynamic sans avoir de mot sur la machine? Effacer l’image sur la boîte à images Random “Une connexion existante a été fermée de force par l’hôte distant.” Après une réinitialisation de TCP Renvoie la vue partielle si l’action est une action ajax ou une action enfant universellement Comment changer l’adresse de mon wsdl Comment sérialiser un object dynamic en JSON dans l’action du contrôleur C # MVC? A quoi sert l’argument de balise protobuf-net SerializeWithLengthPrefix? Obtenir le clic de la boîte de minimisation d’une fenêtre WPF Le moyen le plus rapide de mapper le résultat de SqlDataReader à un object Impossible d’ouvrir le fichier physique Erreur de système d’exploitation 32

Bibliothèque .NET pour les algorithmes de texte?

Connaissez-vous une bibliothèque .NET pour les algorithmes de texte?
En particulier, je m’intéresse aux correspondances de chaînes et aux algorithmes de recherche de texte intégral tels que

  • Algorithme Bitap
  • Levenshtein distance
  • Distance Damerau – Levenshtein

Je sais que celui que j’ai mentionné est assez simple à coder, mais il y a des centaines d’algorithmes de texte, je ne veux pas les coder tous par moi-même.
Si aucune bibliothèque .NET de ce type n’est connue, vous pouvez mentionner la bibliothèque C, C ++, le wrapper de codage sera plus facile que le codage à partir de zéro.

Vous voudrez peut-être consulter la bibliothèque google-diff-match-patch sur Google Code. Ils ont une implémentation de l’algorithme diff de Myer et il prétend implémenter également un algorithme Bitap “au cœur”.

Il contient la source C # que vous recherchez, ainsi que des implémentations en Java, C ++, Lua et Python. Bien que je ne comprenne pas très bien comment utiliser Bitap dans la pratique (il existe des démonstrations dans le projet Google Code), je pense que les fonctions de correspondance commençant à la ligne 1476 de la version actuelle vous intéresseront davantage.

METTRE À JOUR:

Un peu de creusage a trouvé une implémentation de Levenshtein en C # sur CodeProject.

En outre, ce fichier de classe C # contient une implémentation de Levenshtein sur SourceForge. La mise en œuvre fait partie du projet Corsis (aka Tenka Text). L’auteur affirme que la méthode YetiLevenshtein (autour de la ligne 741) est 2x à 10 fois plus rapide que l’implémentation utilisée dans la version CodeProject de l’algorithme référencé ci-dessus.

MISE À JOUR # 2:

Je viens de découvrir l’ implémentation de l’algorithme wikibook avec sa version C # de Levenshtein Distance et j’ai dû l’inclure, car elle a l’air plutôt droit et droit au but. Ce wikibook semble être une excellente référence à garder sous la main en général.

Distance de Levenshtein en C # (avec la permission de Wikibooks) 

private Int32 levenshtein(Ssortingng a, Ssortingng b) { if (ssortingng.IsNullOrEmpty(a)) { if (!ssortingng.IsNullOrEmpty(b)) { return b.Length; } return 0; } if (ssortingng.IsNullOrEmpty(b)) { if (!ssortingng.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)]; }

J’ai réussi à trouver des implémentations de la plupart des algorithmes dont j’ai besoin en combinant WikiPedia + Google Code Search.

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

Bien qu’il soit étrange que personne n’ait créé de projet sur ce sujet, les personnes intéressées pourraient collaborer sur ce sujet.

Si vous faites une correspondance de chaîne, Lucene.Net vaut le détour.

Cependant, je sais que ce n’est pas exactement ce que vous recherchez, et bien que vous puissiez trouver la plupart de ces algorithmes sous une forme quelconque en C #, je ne connais aucune bibliothèque les incorporant bibliothèque).

Par intérêt, pourquoi auriez-vous besoin de plus d’un de ces algorithmes de correspondance complète avec quelques parameters de seuil?

En voici un que j’ai implémenté pour la distance Levenshtein / Damerau – Levenshtein: 

  public static int GetDistance(ssortingng left, ssortingng 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 masortingx = 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]) { masortingx[i, j] = Math.Min(masortingx[i, j], masortingx[i - 2, j - 2] + cost); } } } } return masortingx[lenLeft, lenRight]; }

Je suggère la bibliothèque SimMesortingcs , elle a beaucoup d’algorithmes différents pour la correspondance de chaînes. Disponible aussi sur NuGet .

Brève description:

SimMesortingcs est une bibliothèque de mésortingques de similarité, par exemple d’une distance d’édition (Levenshtein, Gotoh, Jaro, etc.) à d’autres mésortingques (par exemple Soundex, Chapman).

Licence GPLv2.

J’ai trouvé et utilisé la bibliothèque .NET suivante implémentant le mathcing de texte Aho-Corasick de Tom Pesortingcek sur un problème que j’avais. Cela a très bien fonctionné pour moi.