trie oder ausgeglichene binäre Suchbaum zu speichern Wörterbuch?

Ist dies C++, sollten Sie auch berücksichtigen std::tr1::unordered_set. (Falls du C++0x, können Sie std::unordered_set.)

Nur dieses verwendet eine hash-Tabelle intern, das würde ich Wetten, wird aus-üben jeden Baum-wie Struktur in der Praxis. Es ist auch trivial zu implementieren, denn Sie haben nichts zu implementieren.

Eine einfache Lösung ist die Speicherung des dict wie sortiert \n getrennte Wörter auf der Festplatte, in den Arbeitsspeicher zu laden und eine binäre Suche. Die einzige nicht-standard-Teil ist, dass Sie haben, um rückwärts zum Anfang ein Wort, wenn du tust, die binäre Suche.

Hier finden Sie den code! (Es wird davon ausgegangen globals wordlist Hinweis auf die geladene dict, und wordlist_end die Punkte bis kurz nach dem Ende des geladenen dict.

//Return >0 if word > word at position p.
//Return <0 if word < word at position p.
//Return 0 if word == word at position p.
static int cmp_word_at_index(size_t p, const char *word) {
  while (p > 0 && wordlist[p - 1] != '\n') {
    p--;
  }
  while (1) {
    if (wordlist[p] == '\n') {
      if (*word == '\0') return 0;
      else return 1;
    }
    if (*word == '\0') {
      return -1;
    }
    int char0 = toupper(*word);
    int char1 = toupper(wordlist[p]);
    if (char0 != char1) {
      return (int)char0 - (int)char1;
    }
    ++p;
    ++word;
  }
}

//Test if a word is in the dictionary.
int is_word(const char* word_to_find) {
  size_t index_min = 0;
  size_t index_max = wordlist_end - wordlist;
  while (index_min < index_max - 1) {
    size_t index = (index_min + index_max) /2;
    int c = cmp_word_at_index(index, word_to_find);
    if (c == 0) return 1;  //Found word.
    if (c < 0) {
      index_max = index;
    } else {
      index_min = index;
    }
  }
  return 0;
}

Ein großer Vorteil dieses Ansatzes ist, dass die dict gespeichert ist, in einer leicht lesbaren Art und Weise auf der Festplatte, und Sie brauchen keine Phantasie-code, um es zu laden (reserviert einen Speicherblock und read() in one go).

Wenn Sie möchten, verwenden Sie einen trie, könnten Sie einen gepackt und suffix-komprimierte Darstellung. Hier ist ein link zu einer von Donald Knuth ' s Schüler, Franklin Liang, der schrieb über diesen trick in seine Arbeit.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.7018&rep=rep1&type=pdf

Es nutzt die Hälfte der Lagerung von der unkomplizierten textuellen dict-Vertretung gibt Ihnen die Geschwindigkeit eines trie, und Sie können (wie der textuellen dict Vertretung) speichern Sie das ganze auf der Festplatte und laden Sie es in einem gehen.

Den trick verwendet wird, ist zu packen, die trie-Knoten in einem einzigen array, interleaving, wenn möglich. Sowie ein neuer Zeiger (und ein end-of-word-marker-bit) in jeder array-Position wie in einem normalen trie speichern Sie den Brief, den dieser Knoten ist für-diese können Sie sagen, wenn der Knoten gültig ist für Ihren Staat oder, wenn es von einer überlappenden Knoten. Lesen Sie den verlinkten doc für eine vollere und deutlichere Erklärung, als auch einen Algorithmus für die Verpackung der trie in diesem array.

Ist es nicht trivial zu implementieren, das suffix-Komprimierung und gierig packing-Algorithmus beschrieben, aber es ist leicht genug.