Les sous-chaînes les plus populaires

Question

J'essaye d'analyser un grand nombre de chaînes courtes en quelques parties logiques. Cela semble être un problème intéressant que quelqu'un aurait déjà résolu, mais je ne trouve pas de papiers/solutions (ou peut-être que j'essaie de mauvais mots).

Les chaînes contiennent 2 à 5 parties. Si je remplace chaque mot une lettre indiquant que « partie »/« section » il appartient, ici serait un échantillon d'entre eux:

AAABB 
AABBBBCC 
AABBBBDD 
AAACCDD 
... 

La plupart des « sections » ne sont que 2-3 mots et il y a ~ 100-500 occurrences de la même section exacte dans ~ 10k chaînes. Cela signifie qu'il y a AAA == "du texte ici" dans 100 chaînes et AAA == "un autre texte" dans l'autre 100. Dans une chaîne il ne peut y avoir qu'une seule section de chaque type (et elles vont généralement dans l'ordre). Il n'y a pas d'ensemble limité de valeurs pour une section et de nouvelles valeurs peuvent apparaître dans le futur.

Le problème est: comment puis-je détecter de telles sections si j'ai suffisamment d'échantillons et que je ne veux pas les marquer manuellement? Cela peut être supervisé/confirmé, pas entièrement automatique, donc une liste de probabilité est ok. Je pensais simplement faire une liste de 2-5 mots longs n-grammes et trouver la probabilité, mais cela ne prend pas en compte l'ordre (ce qui pourrait être utile). Il détectera également qu'un certain texte est commun, mais si j'ai 2 sections spécifiques avec les mêmes valeurs souvent utilisées, cette méthode ne fonctionnera pas bien. Disons que je n'ai que des chaînes qui se composent de ABCD avec les mêmes valeurs dans toutes les lignes:

ABC 
ABD 
ACD 

Faire seulement ngram analyse, je vais probabilité élevée d'être une section, ainsi que pour AB, C et D Je voudrais éliminer AB des résultats dans ce cas, mais d'une manière qui n'assigne pas sa propre section à des mots comme "the" et élimine toutes les plus grandes sections qui contiennent "the".

Y a-t-il des solutions connues pour des problèmes similaires?

Answer 1

L'algorithme Lempel-Ziv-Welch est très efficace pour identifier les sous-chaînes courantes, mais il n'essaie pas de les classer. Il ne fait pas attention aux limites de mots ou de lignes. Il pourrait toujours être possible de l'utiliser comme point de départ pour obtenir ce dont vous avez besoin.