Méthode efficace de recherche d'un ensemble de chaînes de caractères dans une chaîne de caractères en Java

Question

Je dispose d'un ensemble d'éléments d'une taille d'environ 100 à 200. Soit un échantillon d'éléments X .

Chacun des éléments est un ensemble de chaînes de caractères (le nombre de chaînes dans un tel ensemble est compris entre 1 et 4). X = { s1 , s2 , s3 }

Pour une chaîne d'entrée donnée (environ 100 caractères), disons P Je souhaite vérifier si l'un ou l'autre des X es présent dans la chaîne.

X es présent en P si pour tous les s appartiennent à X , s est une sous-chaîne de P .

L'ensemble des éléments est disponible pour le prétraitement.

---

Je veux que ce soit aussi rapide que possible avec Java. Approches possibles qui ne répondent pas à mes exigences :

• Vérifier si toutes les chaînes s sont des sous-chaînes de P semble être une opération coûteuse
• Parce que s peut être n'importe quelle sous-chaîne de P (pas nécessairement un mot), je ne peux pas utiliser un hachage de mots
• Je ne peux pas utiliser directement les expressions rationnelles comme s1 , s2 , s3 peuvent être présentes dans n'importe quel ordre et toutes les chaînes doivent être présentes en tant que sous-chaînes.

---

Pour l'instant, mon approche consiste à construire une énorme expression rationnelle à partir de chaque X avec toutes les permutations possibles de l'ordre des chaînes. Parce que le nombre d'éléments dans X <= 4, cela reste possible. Ce serait bien si quelqu'un pouvait m'indiquer une meilleure approche (plus rapide/élégante) pour la même chose.

Veuillez noter que l'ensemble des éléments est disponible pour le prétraitement et que je veux la solution en java.

Answer 1

Vous peut utiliser directement les expressions rationnelles :

Pattern regex = Pattern.compile(
    "^               # Anchor search to start of string\n" +
    "(?=.*s1)        # Check if string contains s1\n" +
    "(?=.*s2)        # Check if string contains s2\n" +
    "(?=.*s3)        # Check if string contains s3", 
    Pattern.DOTALL | Pattern.COMMENTS);
Matcher regexMatcher = regex.matcher(subjectString);
foundMatch = regexMatcher.find();

foundMatch est vrai si les trois sous-chaînes sont présentes dans la chaîne.

Notez que vous devrez peut-être échapper vos "chaînes d'aiguilles" si elles peuvent contenir des métacaractères regex.

Answer 2

Il semble que vous optimisiez prématurément votre code avant d'avoir découvert qu'une approche particulière est en fait trop lente.

La propriété intéressante de votre ensemble de chaînes est que la chaîne doit contenir tous les éléments de X en tant que sous-chaîne - ce qui signifie que nous pouvons échouer rapidement si nous trouvons un élément de X qui n'est pas contenue dans P . Cette approche peut s'avérer plus efficace que d'autres pour gagner du temps, en particulier si les éléments de l'analyse de l'information sont bien définis. X sont généralement plus longs que quelques caractères et ne contiennent pas ou peu de caractères répétitifs. Par exemple, un moteur d'expressions rationnelles n'a besoin de vérifier que 20 caractères dans une chaîne de 100 caractères pour vérifier la présence d'une chaîne de 5 caractères non répétitifs (par exemple, côte). Et puisque X a 100-200 éléments que vous voulez vraiment, vraiment échouer rapidement si vous le pouvez.

Ma suggestion serait de trier les chaînes par ordre de longueur et de vérifier chaque chaîne à tour de rôle, en s'arrêtant rapidement si l'une d'entre elles n'est pas trouvée.

Answer 3

Il s'agit d'un cas parfait pour le Algorithme de Rabin-Karp :

Pour la recherche d'un seul motif, Rabin-Karp est inférieur à l'algorithme de Knuth-Morris-Pratt, à l'algorithme de recherche de chaînes de Boyer-Moore et à d'autres algorithmes de recherche de chaînes d'un seul motif plus rapides, en raison de son comportement lent dans le pire des cas. Cependant, Rabin-Karp est un algorithme de choix pour la recherche de motifs multiples.

Answer 4

Lorsque le temps de prétraitement n'a pas d'importance, vous pouvez créer une table de hachage qui associe chaque combinaison d'une lettre, de deux lettres, de trois lettres, etc. qui apparaît dans au moins une chaîne à une liste de chaînes dans lesquelles elle apparaît.

L'algorithme d'indexation d'une chaîne de caractères ressemblerait à ceci (non testé) :

HashMap<String, Set<String>> indexes = new HashMap<String, Set<String>>();

for (int pos = 0; pos < string.length(); pos++) {
    for (int sublen=0; sublen < string.length-pos; sublen++) {
         String substring = string.substr(pos, sublen);
         Set<String> stringsForThisKey = indexes.get(substring);
         if (stringsForThisKey == null) {
             stringsForThisKey = new HashSet<String>();
             indexes.put(substring, stringsForThisKey);
         }
         stringsForThisKey.add(string);
    }
}

L'indexation de chaque chaîne de cette manière serait quadratique par rapport à la longueur de la chaîne, mais elle ne doit être effectuée qu'une seule fois pour chaque chaîne.

Mais le résultat serait un accès rapide et constant à la liste des chaînes de caractères dans lesquelles une chaîne spécifique apparaît.

Answer 5

Vous recherchez probablement Algorithme d'Aho-Corasick qui construit un automate (en forme de triangle) à partir de l'ensemble des chaînes de caractères (dictionnaire) et tente de faire correspondre la chaîne d'entrée au dictionnaire à l'aide de cet automate.