Algorithme de groupement des mots anagrammes

j'ai utilisé un Godel-inspiré schéma:

assignez les nombres premiers P_1 à P_26 aux lettres (dans n'importe quel ordre, mais pour obtenir des valeurs de hachage plus petites, il est préférable de donner des petits nombres premiers aux lettres courantes).

Construit un histogramme des lettres dans le mot.

alors la valeur de hachage est le produit de la prime associée à chaque lettre élevée à la puissance de sa fréquence. Cela donne une valeur unique à chaque anagramme.

code Python:

primes = [2, 41, 37, 47, 3, 67, 71, 23, 5, 101, 61, 17, 19, 13, 31, 43, 97, 29, 11, 7, 73, 83, 79, 89, 59, 53]


def get_frequency_map(word):
    map = {}

    for letter in word:
        map[letter] = map.get(letter, 0) + 1

    return map


def hash(word):
    map = get_frequency_map(word)
    product = 1
    for letter in map.iterkeys():
        product = product * primes[ord(letter)-97] ** map.get(letter, 0)
    return product

ceci habilement transforme le problème délicat de trouver des subanagrammes en le problème (aussi connu pour être délicat) de factoriser de grands nombres...

Une version de Python pour le fou rire:

from collections import defaultdict
res = defaultdict(list)
L = "car, acr, bat, tab, get, cat".split(", ")

for w in L:
    res["".join(sorted(w))].append(w)

print(res.values())

Je ne pense pas que vous trouverez quoi que ce soit de mieux qu'une table de hachage avec une fonction de hachage personnalisé (qui trierait les lettres du mot avant de le hachage).

la somme des lettres ne fonctionnera jamais, parce que vous ne pouvez pas vraiment faire 'ac' et 'bb' différents.

vous aurez besoin de grands entiers (ou un vecteur bit en fait) mais les suivants pourraient fonctionner

la première occurrence de chaque lettre obtient le numéro de bit pour cette lettre, la seconde occurrence obtient le numéro de bit pour cette lettre + 26.

Par exemple

a #1 = 1 b #1 = 2 c #1 = 4 un #2 = 2^26 b #2 = 2 ^ 27

vous pouvez ensuite les additionner ensemble, pour obtenir une valeur unique pour le mot basé sur ses lettres.

votre rangement les exigences pour les valeurs de mot seront:

n * 26 bits

où n est le nombre maximal d'occurrences d'une lettre répétée.

Je n'utiliserais pas le hachage car il ajoute de la complexité pour la recherche et ajoute. Le hachage, le tri et les multiplications seront tous plus lents qu'une simple solution d'histogramme basée sur un réseau avec des uniques de suivi. Pire des cas est O(2n):

// structured for clarity
static bool isAnagram(String s1, String s2)
{
    int[] histogram = new int[256];

    int uniques = 0;

    // scan first string
    foreach (int c in s1)
    {
        // count occurrence
        int count = ++histogram[c];

        // count uniques
        if (count == 1)
        {
            ++uniques;
        }
    }

    // scan second string
    foreach (int c in s2)
    {
        // reverse count occurrence
        int count = --histogram[c];

        // reverse count uniques
        if (count == 0)
        {
            --uniques;
        }
        else if (count < 0) // trivial reject of longer strings or more occurrences
        {
            return false;
        }
    }

    // final histogram unique count should be 0
    return (uniques == 0);
}

j'ai déjà implémenté ceci avec un simple tableau de nombre de lettres, par exemple:

unsigned char letter_frequency[26];

Puis la stocker dans une table de base de données avec chaque mot. Les mots qui ont la même fréquence de lettre 'signature' sont des anagrammes, et une simple requête SQL renvoie alors tous les anagrammes d'un mot directement.

avec quelques expériences avec un très grand dictionnaire, Je n'ai trouvé aucun mot qui dépasse un nombre de fréquence de 9 pour n'importe quelle lettre, de sorte que la 'signature' peut être représentée comme un chaîne de nombres 0..9 (la taille pourrait être facilement réduite de moitié en empaquetant en octets comme hex, et encore réduite en encodant le nombre binaire, mais je n'ai pas pris la peine de tout cela jusqu'à présent).

Voici une fonction ruby pour calculer la signature d'un mot donné et le stocker dans un hachage, tout en éliminant les doublons. Du hachage je construis plus tard une table SQL:

def processword(word, downcase)
  word.chomp!
  word.squeeze!(" ") 
  word.chomp!(" ")
  if (downcase)
    word.downcase!
  end
  if ($dict[word]==nil) 
    stdword=word.downcase
    signature=$letters.collect {|letter| stdword.count(letter)}
    signature.each do |cnt|
      if (cnt>9)
        puts "Signature overflow:#{word}|#{signature}|#{cnt}"
      end
    end
    $dict[word]=[$wordid,signature]
    $wordid=$wordid+1
  end
end

assignez un nombre premier unique aux lettres a-z

itérez votre tableau de mots, en créant un produit de nombres premiers basé sur les lettres de chaque mot.

Stocker ce produit dans votre liste de mots avec le mot correspondant.

trier le tableau, ascendant par le produit.

itérez le tableau, en faisant un contrôle de la pause à chaque changement de produit.

en C, je viens d'implémenter le hachage suivant qui fait essentiellement un bitmask de 26 bits sur si le mot dans le dictionnaire a une lettre particulière en elle. Tous les anagrammes ont le même hachage. Le hachage ne prend pas en compte les lettres répétées, donc il y aura une surcharge supplémentaire, mais il parvient quand même à être plus rapide que mon implémentation perl.

#define BUCKETS 49999

struct bucket {
    char *word;
    struct bucket *next;
};

static struct bucket hash_table[BUCKETS];

static unsigned int hash_word(char *word)
{
    char *p = word;
    unsigned int hash = 0;

    while (*p) {
        if (*p < 97 || *p > 122) {
            return 0;
        }
        hash |= 2 << (*p - 97);
        *p++;
    }

    return hash % BUCKETS;
}

seaux surchargés créés et ajoutés en tant que liste liée, etc. Alors il suffit d'écrire une fonction qui fait en sorte que le les mots qui correspondent à la valeur de hachage sont de la même longueur et que les lettres dans chacun sont 1 à 1 et retourner que comme une correspondance.

je vais générer le hasmap basé sur le mot échantillon et le reste des alphabets Je ne m'en soucierai pas.

Par exemple, si le mot est "voiture" ma table de hachage sera comme ceci: a, 0 b, MAX c, 1 d, MAX e, MAX ... .. r, 2 . Par conséquent, toute valeur supérieure à 3 considérera comme non conforme

(plus de réglage...) Et ma méthode de comparaison comparera le total de hash dans le calcul de hash lui-même. Il ne pourra pas continuer une fois qu'il peut identifier le mot n'est pas égal.

public static HashMap<String, Integer> getHashMap(String word) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        String[] chars = word.split("");
        int index = 0;
        for (String c : chars) {
            map.put(c, index);
            index++;
        }
        return map;
    }

    public static int alphaHash(String word, int base,
            HashMap<String, Integer> map) {
        String[] chars = word.split("");
        int result = 0;
        for (String c : chars) {
            if (c.length() <= 0 || c.equals(null)) {
                continue;
            }
            int index = 0;
            if (map.containsKey(c)) {
                index = map.get(c);
            } else {
                index = Integer.MAX_VALUE;
            }
            result += index;
            if (result > base) {
                return result;
            }
        }
        return result;
    }

méthode principale

  HashMap<String, Integer> map = getHashMap(sample);
        int sampleHash = alphaHash(sample, Integer.MAX_VALUE, map);
        for (String s : args) {
                if (sampleHash == alphaHash(s, sampleHash, map)) {
                    System.out.print(s + " ");
                }
            }

les anagrammes peuvent être trouvés de la manière suivante:

1. la longueur du mot devrait correspondre.
2. effectuer l'addition de chaque caractère en termes de valeur entière. Cette somme correspond si vous effectuez la même sur anagramme.
3. effectuer la multiplication de chaque caractère en termes de valeur entière. Valeur évaluée correspond si vous effectuez la même sur anagramme.

donc j'ai réfléchi à travers trois validations, nous pouvons trouver des anagrammes. Corrigez-moi si je suis mauvais.

exemple: abc cba

longueur des deux mots est de 3.

la somme des caractères individuels pour les deux mots est de 294.

Prod des caractères individuels pour les deux mots est 941094.

version JavaScript. utilisant le hachage.

complexité temporelle: 0 (nm), où n est le nombre de mots, m est la longueur du mot

var words = 'cat act mac tac ten cam net'.split(' '),
    hashMap = {};

words.forEach(function(w){
    w = w.split('').sort().join('');
    hashMap[w] = (hashMap[w]|0) + 1;
});

function print(obj,key){ 
    console.log(key, obj[key]);
}

Object.keys(hashMap).forEach(print.bind(null,hashMap))

je veux juste ajouter une solution python simple en plus des autres réponses utiles:

def check_permutation_group(word_list):
    result = {}

    for word in word_list:
        hash_arr_for_word = [0] * 128  # assuming standard ascii

        for char in word:
            char_int = ord(char)
            hash_arr_for_word[char_int] += 1

        hash_for_word = ''.join(str(item) for item in hash_arr_for_word)

        if not result.get(hash_for_word, None):
            result[str(hash_for_word)] = [word]
        else:
            result[str(hash_for_word)] += [word]

return list(result.values())

code python:

line = "man car kile arc none like"
hmap = {}
for w in line.split():
  ws = ''.join(sorted(w))
  try:
    hmap[ws].append(w)
  except KeyError:
    hmap[ws] = [w]

for i in hmap:
   print hmap[i]

sortie:

['car', 'arc']
['kile', 'like']
['none']
['man']