Algorithmus zum Gruppieren von Anagrammwörtern

Question

Bei einer Reihe von Wörtern müssen wir die Anagrammwörter finden und jede Kategorie alleine mithilfe des besten Algorithmus anzeigen.

Eingabe:

man car kile arc none like

Ausgabe:

man
car arc
kile like
none

Die beste Lösung, an der ich gerade arbeite, basiert auf einer Hashtabelle, aber ich überlege, wie ich eine Gleichung entwickeln kann, um Anagrammwörter in einen ganzzahligen Wert umzuwandeln.

Beispiel: man => 'm'+'a'+'n' aber das würde keine eindeutigen Werte liefern.

Irgendwelche Vorschläge?

---

Sieh dir den folgenden Code in C# an:

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

}

Das Problem besteht darin, die Methode GetUniqueInts(string []) zu entwickeln.

Answer 1

Ich würde kein Hashing verwenden, da es zusätzliche Komplexität für die Suche hinzufügt. Hashing, Sortieren und Multiplikationen werden alle langsamer sein als eine einfache Array-basierte Histogrammlösung mit der Verfolgung von eindeutigen Elementen. Schlimmstenfalls beträgt die Laufzeit O(2n):

// für Klarheit strukturiert
static bool isAnagram(String s1, String s2)
{
    int[] histogramm = new int[256];

    int eindeutige = 0;

    // erste Zeichenkette durchsuchen
    foreach (int c in s1)
    {
        // Anzahl der Vorkommen zählen
        int anzahl = ++histogramm[c];

        // eindeutige Elemente zählen
        if (anzahl == 1)
        {
            ++eindeutige;
        }
    }

    // zweite Zeichenkette durchsuchen
    foreach (int c in s2)
    {
        // Anzahl der Vorkommen umkehren
        int anzahl = --histogramm[c];

        // Anzahl der eindeutigen Elemente umkehren
        if (anzahl == 0)
        {
            --eindeutige;
        }
        else if (anzahl < 0) // trivial Ablehnung längerer Zeichenketten oder häufigerer Vorkommen
        {
            return false;
        }
    }

    // Die endgültige Anzahl der eindeutigen Elemente im Histogramm sollte 0 sein
    return (eindeutige == 0);
}

Answer 2

Ich habe das bereits einmal mit einem einfachen Array von Buchstabenfrequenzen implementiert, z. B.:

unsigned char Buchstabenfrequenz[26];

Dann speichern Sie dies in einer Datenbanktabelle zusammen mit jedem Wort. Wörter, die die gleiche Buchstabenfrequenz 'Signatur' haben, sind Anagramme, und eine einfache SQL-Abfrage liefert direkt alle Anagramme eines Wortes.

Mit etwas Experimentieren mit einem sehr großen Wörterbuch fand ich kein Wort, das einen Frequenzzähler von 9 für irgendeinen Buchstaben überschritten hat, daher kann die 'Signatur' als eine Zeichenfolge von Zahlen 0..9 dargestellt werden (Die Größe könnte leicht halbiert werden, indem sie in Bytes als Hexadezimalzahl gepackt wird, und weiter reduziert werden, indem die Nummer binär codiert wird, aber bisher habe ich mich noch nicht darum gekümmert).

Hier ist eine Ruby-Funktion zum Berechnen der Signatur eines gegebenen Wortes und zum Speichern in einem Hash, wobei Duplikate verworfen werden. Aus dem Hash baue ich später eine SQL-Tabelle:

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

Answer 3

Weisen Sie jedem Buchstaben von a-z eine eindeutige Primzahl zu

Durchlaufen Sie Ihr Wortarray und erstellen Sie ein Produkt von Primzahlen basierend auf den Buchstaben in jedem Wort.
Speichern Sie dieses Produkt in Ihrer Wortliste zusammen mit dem entsprechenden Wort.

Sortieren Sie das Array aufsteigend nach dem Produkt.

Durchlaufen Sie das Array und machen Sie bei jeder Produktänderung einen Kontrollabbruch.

Answer 4

In C habe ich gerade den folgenden Hash implementiert, der im Grunde genommen einen 26-Bit-Bitmask auf das Wort im Wörterbuch anwendet, um festzustellen, ob ein bestimmter Buchstabe darin vorkommt. Somit haben alle Anagramme denselben Hash. Der Hash berücksichtigt nicht wiederholte Buchstaben, daher wird es einige zusätzliche Überlastung geben, aber er ist dennoch schneller als meine Perl-Implementierung.

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

Überlastete Buckets erstellt und als verkettete Liste hinzugefügt, usw. Dann schreibe einfach eine Funktion, die sicherstellt, dass die Wörter, die den Hash-Wert übereinstimmen, die gleiche Länge haben und dass die Buchstaben in jedem 1 zu 1 sind und gib das als Übereinstimmung zurück.

Answer 5

Ich werde die Hasmap basierend auf dem Beispielswort generieren, und den Rest des Alphabets werde ich ignorieren.

Zum Beispiel, wenn das Wort "Auto" ist, meine Hashtabelle wird wie folgt aussehen: a,0 b,MAX c,1 d,MAX e,MAX ... .. r,2 . Jede Hashgröße über 3 wird als nicht übereinstimmend betrachtet

(Weitere Anpassungen...) Und meine Vergleichsmethode wird den Hash-Gesamtwert innerhalb der Hash-Berechnung selbst vergleichen. Es wird nicht weitermachen, sobald es feststellen kann, dass das Wort nicht übereinstimmt.

public static HashMap getHashMap(String word) {
        HashMap map = new HashMap();
        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 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;
    }

Hauptmethode

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