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

L'une des méthodes consiste à générer toutes les sous-chaînes possibles et à les ajouter à un ensemble. Cette méthode est assez inefficace.

Au lieu de cela, vous pouvez créer toutes les chaînes de caractères depuis n'importe quel point jusqu'à la fin dans un NavigableSet et rechercher la correspondance la plus proche. Si la correspondance la plus proche commence par la chaîne que vous recherchez, vous avez une correspondance de sous-chaîne.

static class SubstringMatcher {
    final NavigableSet<String> set = new TreeSet<String>();

    SubstringMatcher(Set<String> strings) {
        for (String string : strings) {
            for (int i = 0; i < string.length(); i++)
                set.add(string.substring(i));
        }
        // remove duplicates.
        String last = "";
        for (String string : set.toArray(new String[set.size()])) {
            if (string.startsWith(last))
                set.remove(last);
            last = string;
        }
    }

    public boolean findIn(String s) {
        String s1 = set.ceiling(s);
        return s1 != null && s1.startsWith(s);
    }
}

public static void main(String... args) {
    Set<String> strings = new HashSet<String>();
    strings.add("hello");
    strings.add("there");
    strings.add("old");
    strings.add("world");
    SubstringMatcher sm = new SubstringMatcher(strings);
    System.out.println(sm.set);
    for (String s : "ell,he,ow,lol".split(","))
        System.out.println(s + ": " + sm.findIn(s));
}

empreintes

[d, ello, ere, hello, here, ld, llo, lo, old, orld, re, rld, there, world]
ell: true
he: true
ow: false
lol: false

Answer 2

Vous pouvez également envisager d'utiliser un "arbre des suffixes". Je n'ai pas utilisé ce code, mais il en existe un qui est décrit comme suit aquí

J'ai utilisé des implémentations propriétaires (auxquelles je n'ai même plus accès) et elles sont très rapides.