C# le code / Algorithme de recherche de terminal dans le texte

On a 5 MB de texte typique /Juste des mots simples/. On a 1000 mots / phrases qui peuvent être utilisées comme terme pour rechercher dans ce texte.

Quel est le moyen le plus efficace de le faire dans .NET /à la perfection C#/?

Nos idées incluent regex /Un, beaucoup/ Plus même String.Contains Matériel.

Les données d'entrée représentent une chaîne de texte 2 Mb 5 Mb - tout le texte. Plusieurs hits sont bons, car dans chaque terme /de 1000/, Ce qui coïncide, nous voulons vraiment savoir à ce sujet. Performance du point de vue de toute exécution de temps, ne prenez pas soin de la piste. L'algorithme actuel donne 60 secondes + en utilisant naïf string.contains. Nous ne voulons pas 'cat' Compatible 'category' ou même 'cats' /C'est-à-dire que l'ensemble du terme du terme devrait tomber, sans stembra/.

Nous attendons le taux de frappe <5% dans le texte. Idéalement, les résultats seraient simplement un terme coïncident /Ne pas avoir besoin d'une position ou d'une fréquence/. Nous obtenons une nouvelle chaîne 2-5mb Tout le monde 10 Secondes, nous ne pouvons donc pas supposer que nous pouvons indexer les données d'entrée. 1000 Les termes sont dynamiques, bien qu'il y ait des vitesses de changement 1 Changements par heure.
Invité:

Gregoire

Confirmation de:

Naïve string.Contains avec 762 dans les mots /la dernière page/ "Guerres et mira" /3.13MB/ passe pour moi environ à travers 10 secondes. Allumer 1000 GUIDs Cela arrive quelque chose pour 5.5 donne moi une seconde.

Regex.IsMatch a trouvé 762 les mots /dont la plupart étaient probablement aussi sur les pages précédentes/ Environ pour .5 Secondes et exclu GUIDs derrière 2.5 secondes.

Je suggérerais que votre problème soit que vous avez juste besoin d'un équipement décent.

Camille

Confirmation de:

Pourquoi réinventer le vélo? Pourquoi pas simplement utiliser quelque chose comme
http://incubator.apache.org/lucene.net/
?

Alice

Confirmation de:

Avez-vous envisagé ce qui suit:

Vous inquiétez-vous la sous-chaîne? Supposons que je cherche un mot "cat", Ni plus ni moins. Maintenant considérer l'algorithme Knuth-Morris-Pratt ou string.contains pour "concatinate". Les deux seront retournés true /ou index/. c'est normal?

De plus, vous devrez examiner l'idée de la principale ou de "Finite" Statut d'état. Regardons à nouveau "diary", Offre de test - "there are many kinds of diaries". Eh bien, pour nous avec vous il y a un mot "38", Est-ce pris en compte? Si tel est le cas, nous devrons alors pré-traiter la proposition, transformer des mots à l'état final /Agendas -> un journal/, Et l'offre deviendra "there are many kind of diary". Maintenant, on peut dire que le journal est dans le centre /S'il vous plaît regarder le porteur timmer algroratm/

De plus, en ce qui concerne le traitement du texte/ Il pareil Natrual Langauge Processing/, Vous pouvez supprimer certains mots comme bruit, par exemple, "a, have, you, I, me, some, to" <- Ils peuvent être considérés comme des mots inutiles, puis peuvent être retirés avant que tout traitement ne se produise? par exemple

"J'ai écrit plusieurs aujourd'hui C#", Si j'avais 10 000 Travaux clés pour la recherche, je devrais numériser toute l'offre 10 000 x Le nombre de mots dans la phrase. Supprimer le bruit avant la main réduira le temps de traitement

"Posté C# Aujourd'hui" <- J'ai enlevé le bruit, maintenant il y a une montre moins.

Grand article O. NLP Peut être trouvé ici.
http://www.codeproject.com/KB/ ... .aspx
Cégatitude

HTH

Des os

Catherine

Confirmation de:

Modifié
http://en.wikipedia.org/wiki/Suffix_tree
Ce serait très rapide, bien que cela faudrait beaucoup de mémoire, et je ne sais pas à quelle vitesse il pourrait être construit. Après cela, cependant, chaque recherche prendra O /1/.

Eugene

Confirmation de:

Essayez-vous d'obtenir une liste de mots correspondants ou essayez de les mettre en surbrillance dans le texte, d'obtenir le début et la longueur de la position de coïncidence? Si tout ce que vous essayez de faire est de savoir s'il ya des mots, vous pouvez utiliser la théorie des sous-ensembles pour le remplir de manière assez efficace.

Cependant, je m'attends à ce que vous essayiez de déterminer la position initiale de chaque match dans le texte ... Dans ce cas, cette approche ne fonctionnera pas.

L'approche la plus efficace que je puisse inventer - Il est de créer de manière dynamique le motif de conformité à l'aide de la liste, puis d'utiliser regex. Il est beaucoup plus facile de soutenir une liste de 1000 éléments que le modèle de soutien regex, Basé sur le même 1000 Éléments.

Pour autant que je comprends, Regex utilise le même algorithme KMP, proposé pour un traitement efficace de grandes quantités de données , Par conséquent, si vous n'avez vraiment pas besoin de creuser et de comprendre les détails de la façon dont cela fonctionne /Qu'est-ce qui peut être utile pour la croissance personnelle/, alors peut-être regex sera OK.

Il existe un article assez intéressant sur les algorithmes pour trouver de nombreux modèles dans de grands fichiers:
http://webglimpse.net/pubs/TR94-17.pdf

Gilles

Confirmation de:

Voici une autre idée: faire une classe environ comme suit:


class Word
{
string Word;
List<int> Positions;
}


Pour chaque mot unique dans votre texte, vous créez une instance de cette classe. Déployer Positions stockera des positions /compté en mots et pas en caractères/ Du début du texte, où ce mot a été trouvé.

Ensuite, faites deux autres listes qui serviront d'index. On stockera toutes ces classes triés par leurs textes, l'autre - Par leurs positions dans le texte. En substance, l'index de texte sera probablement SortedDictionary, Tandis que l'index de position sera simple
List<word>

.

Ensuite, pour trouver la phrase, vous le cassez des mots. Trouvez le premier mot dans le dictionnaire /c'est O /log /n///. De là, vous savez quel type de mots possibles le suivez dans le texte /vous avez de la gamme de postes/. Regarde ces mots /Utilisez l'index de position pour les trouver dans O /1// Et continuer jusqu'à ce que vous trouviez une ou plusieurs coïncidences complètes.
</word></int>

Daniel

Confirmation de:

Est-ce un goulot d'étranglement? Combien de temps cela prendra-t-il? 5 MiB En fait, il n'y a pas beaucoup de données de recherche. Les expressions régulières peuvent fonctionner simplement excellentes, surtout si vous encodez toutes les chaînes de recherche dans

une

Modèle avec alternance. Il déprime fondamentalement le coût total de la recherche O /n + m/, Où la n-longueur de votre texte et la longueur m de tous les modèles pris ensemble. Veuillez noter que c'est une très bonne idée.

Une alternative qui convient bien à de nombreux modèles est
http://en.wikipedia.org/wiki/Agrep
. J'ai déjà publié un très simplifié
https://coderoad.ru/154365/
.

Babette

Confirmation de:

Eh bien, la modification actuelle montre cela comme le plus rapide /psuedocode/:


foreach /var term in allTerms/
{
string pattern = term.ToWord//; // Use /b word boundary regex
Regex regex = new Regex/pattern, RegexOptions.IgnoreCase/;
if /regex.IsMatch/bigTextToSearchForTerms//
{
result.Add/term/;
}
}


Qu'est-ce qui était incroyable /au moins pour moi!/ , donc c'est ce que le lancement regex à 1000 Une fois qu'il était plus rapide qu'un regex avec 1000 alternatives, c'est "/b term1 /b | /b term2 /b | /b termN /b" puis essayer d'utiliser regex.Matches.Count

Gaetan

Confirmation de:

Comment ça marche en comparaison? Il utilise LINQ, Donc, il peut être un peu plus lent, pas sûr ...


List<string> allTerms = new List<string>/new String//{"string1", "string2", "string3", "string4"}/;
List<string> matches = allTerms.Where/item =&gt; Regex.IsMatch/bigTextToSearchForTerms, item, RegexOptions.IgnoreCase//;


Il utilise des prédicats classiques pour mettre en œuvre la méthode FIND, Donc, il devrait être plus rapide que LINQ:


static bool Match/string checkItem/
{
return Regex.IsMatch/bigTextToSearchForTerms, checkItem, RegexOptions.IgnoreCase/;
}

static void Main/string[] args/
{
List<string> allTerms = new List<string>/new String//{"string1", "string2", "string3", "string4"}/;
List<string> matches = allTerms.Find/Match/;
}


Ou il utilise la syntaxe lambda Mettre en œuvre un prédicat classique, qui devrait être plus rapide que LINQ, Mais plus lisible que la syntaxe précédente:


List<string> allTerms = new List<string>/new String//{"string1", "string2", "string3", "string4"}/;
List<string> matches = allTerms.Find/checkItem =&gt; Regex.IsMatch/bigTextToSearchForTerms, checkItem, RegexOptions.IgnoreCase//;


Je n'ai testé aucun d'entre eux pour la performance, mais tous implémentent votre idée d'itération sur la liste de recherche en utilisant regex. Ce sont simplement des méthodes différentes de sa mise en œuvre.
</string></string></string></string></string></string></string></string></string>

Pour répondre aux questions, connectez-vous ou registre