Algoritmo per raggruppare le parole anagramma

StackOverflow https://stackoverflow.com/questions/396005

Domanda

Dato un insieme di parole, abbiamo bisogno di trovare le parole anagramma e visualizzare ogni categoria da solo utilizzando il miglior algoritmo.

ingresso: 

man car kile arc none like

uscita: 

man
car arc
kile like
none

La soluzione migliore che sto sviluppando la società si basa su una tabella hash, ma sto pensando di equazione per convertire parola anagramma in valore intero.

Esempio:. Man => 'm' + 'a' + 'n', ma questo non darà valori unici

Ogni suggerimento?

Vedi seguente codice in C #: 

string line = Console.ReadLine();
string []words=line.Split(' ');
int[] numbers = GetUniqueInts(words);
for (int i = 0; i < words.Length; i++)
{
    if (table.ContainsKey(numbers[i]))
    {
        table[numbers[i]] = table[numbers[i]].Append(words[i]);
    }
    else
    {
        table.Add(numbers[i],new StringBuilder(words[i]));
    }

}

Il problema è come sviluppare il metodo GetUniqueInts(string []).

È stato utile?

Soluzione

Non perdete tempo con una funzione di hash personalizzato a tutti. Utilizzare la normale funzione di stringa di hash su qualunque sia la vostra piattaforma è. La cosa importante è quello di rendere la chiave per la vostra tabella di hash l'idea di una "parola ordinato" - dove la parola è ordinato per lettera, in modo da "auto" => "acr". Tutti gli anagrammi avranno lo stesso "di parole ordinate".

Basta avere un hash da "parole ordinate" a "elenco di parole per quella parola ordinato". In LINQ questo è incredibilmente facile: 

using System;
using System.Collections.Generic;
using System.Linq;

class FindAnagrams
{
    static void Main(string[] args)
    {
        var lookup = args.ToLookup(word => SortLetters(word));

        foreach (var entry in lookup)
        {
            foreach (var word in entry)
            {
                Console.Write(word);
                Console.Write(" ");
            }
            Console.WriteLine();
        }
    }

    static string SortLetters(string original)
    {
        char[] letters = original.ToCharArray();
        Array.Sort(letters);
        return new string(letters);
    }
}

uso Esempio: 

c:\Users\Jon\Test>FindAnagrams.exe man car kile arc none like
man
car arc
kile like
none

Altri suggerimenti

Ho usato uno schema di Godel di ispirazione:

Assegnare il primi P_1 per P_26 alle lettere (in qualsiasi ordine, ma per ottenere i valori hash smallish migliori per dare le lettere comuni piccoli numeri primi).

costruito un istogramma delle lettere della parola.

Quindi il valore hash è il prodotto di primaria associata di ogni lettera elevato alla potenza della sua frequenza. Questo dà un valore unico per ogni anagramma.

codice 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

Questo trasforma abilmente il problema difficile di trovare subanagrams nel (anche noto per essere difficile) problema di factoring grandi numeri ...

Una versione Python per risatine: 

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())

Non credo che troverete qualcosa di meglio di una tabella hash con una funzione di hash personalizzato (che sarebbe ordinare le lettere di lui parola prima di hashing).

Somma delle lettere non funzionerà mai, perché non si può davvero fare 'ac' e 'bb' diverso.

Avrete bisogno di grandi numeri interi (o un vettore di bit in realtà), ma il seguente potrebbe funzionare

la prima occorrenza di ogni lettera get assegnato il numero di bit per quella lettera, la seconda occorrenza ottiene il numero di bit per quella lettera + 26.

Ad esempio

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

È quindi possibile sommare questi insieme, per ottenere un valore univoco per la parola sulla base di esso è lettere.

I tuoi requisiti di archiviazione per i valori di parola saranno:

n * 26 bit

dove n è il numero massimo di occorrenze di qualsiasi lettera ripetuta.

Non vorrei usare l'hashing dal momento che aggiunge ulteriore complessità per i look-up e aggiunge. Hashing, smistamento e moltiplicazioni sono tutti andando essere più lenta di una soluzione semplice istogramma basata su array con unici inseguimento. Caso peggiore è 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);
}

Ho implementato questo prima con un semplice array di lettera conta, per esempio:. 

unsigned char letter_frequency[26];

Poi memorizzare che in una tabella del database insieme a ogni parola. Le parole che hanno la stessa lettera di frequenza 'firma' sono anagrammi, e una semplice query SQL quindi restituisce tutti gli anagrammi di una parola direttamente.

Con un po 'di sperimentazione con un dizionario molto grande, ho trovato nessuna parola che ha superato un conteggio di frequenza di 9 per qualsiasi lettera, in modo che il 'firma' può essere rappresentato come una stringa di numeri 0..9 (La dimensione può essere facilmente dimezzato da imballaggio in byte come esadecimale, e ulteriormente ridotto dal binario codifica il numero, ma non ho disturbato con tutto questo finora).

Ecco una funzione rubino per calcolare la firma di una data parola e conservarla in un hash, scartando i duplicati. Dal Hash ho poi costruire una tabella di 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

Assegnare un numero primo unica per le lettere a-z

Scorrere l'array parola, la creazione di un prodotto di numeri primi in base alle lettere in ogni parola.
Conservare il prodotto nella tua lista di parole, con la parola corrispondente.

ordinare l'array, salendo dal prodotto.

Scorrere la matrice, facendo un pausa controllo ad ogni cambio di prodotto.

In C, ho appena realizzato le seguenti hash che fa fondamentalmente un 26-bit maschera di bit se la parola nel dizionario ha una particolare lettera in esso. Quindi, tutti gli anagrammi hanno lo stesso hash. L'hash non tiene conto ripetute lettere, quindi ci sarà qualche sovraccarico aggiuntivo, ma riesce ancora a essere più veloce di mia implementazione 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;
}

secchi overload creati e aggiunti come lista collegata, ecc Poi basta scrivere una funzione che fa in modo che le parole che corrispondono al valore di hash sono la stessa lunghezza e che le lettere a ciascuno sono 1 a 1 e ritorno che come un fiammifero .

I genererà il hasmap basata sulla parola del campione e il resto degli alfabeti non mi importa.

Per esempio, se la parola è "auto" la mia tabella di hash sarà simile a questo: a, 0 b, MAX c, 1 d, MAX e, MAX ... .. r, 2 . Di conseguenza ha alcun superiore a 3 considererà come non corrispondenti

(più di sintonia ...) E il mio metodo di confronto sarà confrontare il totale hash all'interno del calcolo dell'hash stesso. Non continuerà una volta in grado di identificare la parola non è uguale. 

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;
    }

metodo Main 

  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 + " ");
                }
            }

Anagrammi possono essere trovati nel seguente modo:

  1. Lunghezza di parola dovrebbe corrispondere.
  2. Eseguire aggiunta di ogni personaggio in termini di valore intero. Tale somma corrisponderà se si esegue lo stesso su anagramma.
  3. Eseguire moltiplicazione di ciascun carattere in termini di valore intero. valore valutato corrisponderà se si esegue lo stesso su anagramma.

Così ho pensato che attraverso più di tre convalide, possiamo trovare anagrammi. Correggetemi se sbaglio.

Esempio: ABC CBA

Lunghezza di entrambe le parole è 3.

Somma dei singoli caratteri per entrambe le parole è 294.

Prod dei singoli caratteri per entrambe le parole è 941094.

Voglio solo aggiungere soluzione python semplice in aggiunta alle altre risposte utili: 

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())

codice 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]

uscita: 

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

Versione JavaScript. utilizzando l'hashing.

Ora Complessità: 0 (nm), dove n è il numero di parole, m è la lunghezza della parola 

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))
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top