Recherche d'anagrammes et de sabanagrammes dans tous les mots de la langue

La résolution de problèmes avec les anagrammes a conduit à l'idée:
Combien de mots restent si vous supprimez toutes les anagrammes et les sangangrammes du dictionnaire de la langue russe

Le dictionnaire contient plus de 1,5 million de mots sous différentes formes.

Vous pouvez comparer chaque mot avec chacun, mais pour 1,5 million d'entrées, il est long et pas optimal.
Dans un monde avec une mémoire infinie, vous pouvez générer des sous-chaînes de toutes les permutations de chaque mot et consulter notre dictionnaire dessus,

mais y a-t-il une meilleure solution ?

Commençons par la terminologie:

Anagramme - un mot obtenu par réarrangement des lettres
Exemple: fusée et chariot

Sabanagramme - un mot qui peut être composé de lettres d'un autre mot
Exemple: arc - sabanagramme du mot fusée

Tâche :

Disons que notre dictionnaire se compose de cinq mots difficiles:

fusée , chariot , arcade , cat , crachat

Ajouter un dictionnaire à l' arbre de préfixe (Trie)
Chaque nœud d'arbre contient une paire: lettre + son numéro dans le mot
Les nœuds sont triés par ordre alphabétique et par la fréquence de la lettre dans le mot



Algorithme (sous forme simplifiée):

Prenez la parole, n.r. cat:

Nous recherchons des nœuds commençant par la lettre minimale du mot ("k")

(Dans la figure, ces nœuds sont marqués en violet)

Dès que nous trouvons un tel nœud, nous recherchons dans le sous-arbre le chemin contenant les lettres restantes dans la quantité requise

Dans le mot crachat sous le nœud K-1, il y a O-2 et T-1, ce qui est suffisant pour notre mot chat.

L'avantage d'une telle structure de données est que nous pouvons rapidement quitter le sous-arbre si la lettre du nœud> que la lettre que nous regardons

. Après avoir vérifié notre dictionnaire, nous avons découvert que seul le crachat n'est pas une anagramme ou sabanagramme d'un autre mot

Code Java
 public boolean isAnagramOrSubAnagram(Word word) {
        Character minCharacter = word.getMinCharacter();

        Stack<TrieNode> stack = new Stack<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            TrieNode node = stack.pop();

            for (Entry<TrieKey, TrieNode> entry : node.getChildren().entrySet()) {
                char character = entry.getKey().getCharacter();
                if (character < minCharacter) {
                    stack.add(entry.getValue());
                } else if (character > minCharacter) {
                    break;
                } else if (entry.getKey().getCount() >= word.getCharacterCount(minCharacter)) {
                    if (doesMinWordCharacterNodeContainAnagram(entry, word)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }



→ La version complète du code avec deux dictionnaires et tests

PS

Pour un dictionnaire russe de 1,5 million, 242399 mots restants en 13 minutes
Pour un dictionnaire anglais de 416 mille laissé 49251 en 45 secondes

Vous pouvez optimiser le dictionnaire d'origine en supprimant le mot actuel si le suivant commence par lui

All Articles