Nombre de sous-zone

Question

Le problème est une variante du comptage de sous-réseau. Donné un tableau de nombres, disons, 1,2,2,3,2,1,2,2,2,2 je cherche des sous-réseaux et compte la fréquence de chacun. Je commence par regarder à partir de K longueur sous-matrices (exemple K = 3).

Le nombre de sous-zone 1,2,2 est C1:2.

Le nombre de sous-matrices 2,2,3 est 1.

Le nombre de sous-zone 2,3,2 est 1.

et ainsi de suite.

Maintenant, je cherche des sous-matrices de longueur 2. Le nombre de sous-zone 1,2 est C2: 2. Mais (1,2) est un sous-ensemble du sous-ensemble 1,2,2. Donc, je calcule son nombre en soustrayant C1 de C2 qui donne le nombre de 1,2 comme 0. De même, compte 2,2 est 1. Mon problème est dans la gestion des cas où plus d'un sous-ensemble parent existe. Je ne considère pas les sous-réseaux dans mon jeu de résultats dont la fréquence sort à 1. Exemple: 1,2,3,1,2,3,1,2,2,3

Ici, comte de 1,2,3 est 2. Le nombre de 2,3,1 est 2.

Maintenant, quand je cherche le nombre de 2,3, il devrait être 1 car tous les parents de plus grande longueur ont couvert les occurrences. Comment dois-je gérer ces cas?

L'approche que je pensais était de marquer toutes les occurrences de modèle du parent. Dans le cas ci-dessus, marquez toutes les occurrences de 1,2,3 et 2,3,1. Tableau ressemble à ceci:

1,2,3,1,2,3,1,2,2,3

X,X,X,X,X,X,X,2,2,3

où X représente la position marquée. Maintenant, la fréquence de 2,3 nous voyons est 1 selon les positions qui ne sont pas marquées. Donc, fondamentalement, je marque toutes les occurrences de motif que je trouve à l'étape actuelle. Pour la prochaine étape, je commence à chercher des modèles à partir des emplacements non marqués seulement pour obtenir le compte correct.

Je fais face à de grandes données sur lesquelles cela semble un peu pas si bon à faire. De plus, je ne suis pas sûr que ce soit correct ou non. D'autres approches ou idées peuvent-elles être d'une grande aide?

Answer 1

Construire suffix array pour un tableau donné.

Pour nombre tous les répéter avec lengt donné sous-tableaux h - marcher à travers ce tableau suffixe, comparant suffixes voisin par la longueur de préfixe nécessaire.
Pour votre premier exemple

source array 
1,2,2,3,2,1,2,2,2,2 
suffix array is 
5,0,9,4,8,7,6,1,2,3: 

1,2,2,2,2    (5) 
1,2,2,3,2,1,2,2,2,2 (0) 
2      (9) 
2,1,2,2,2,2   (4) 
2,2     (8) 
2,2,2     (7) 
2,2,2,2    (6) 
2,2,3,2,1,2,2,2,2  (1) 
2,3,2,1,2,2,2,2  (2) 
3,2,1,2,2,2,2   (3) 

Avec une longueur de 2, nous pouvons compter deux sous-réseaux 1,2 et quatre sous-tableaux 2,2

Si vous voulez compter une sous-tableau donné - par exemple, tous les suffixes commençant par (1,2), utilisez simplement la recherche binaire pour obtenir le premier et le dernier index (comme les opérations std:upperbound et std:lowerbound en C++ STL).
Pour les mêmes exemples index des premiers et derniers événements de (1,2)dans le tableau de suffixe sont 0 et 1, donc le nombre est last-first+1=2