运行时 Trie 数据结构生成与存储和读取文件方法

Question

我正在为英语词典中的每个单词创建一个 Trie 结构。我想将这种结构用于单词搜索和拼字游戏等游戏，但我不知道在运行时生成结构是否更快，或者我是否应该想出一种方法将这种 Trie 结构扁平化为 JSON 或 XML 在运行时读入内存。

我不太了解创建数据库或存储数据供以后使用，所以任何建议都很棒 - 现在我正在查看 Jackson 和 Java。最终目标是将此应用程序移植到我网站上的 JavaScript。

Answer 1

这就是您如何生成 Trie 结构并在您的网站上使用它而无需使用 Java，只需使用 JavaScript。具有两种方法的简单 Trie 结构：insert 和 search 在 JS 中可能如下所示：

function Trie() {
    this.root = new TrieNode();
    this.insert = function(key) { 
        let length = key.length, next = this.root; 

        for (let level = 0; level < length; level++) { 
            let character = key.charAt(level); 
            if (next.children[character] == null) {
                next.children[character] = new TrieNode(); 
            }

            next = next.children[character]; 
        }
        next.endOfWord = true; 
    }
    this.search = function(key) { 
        let length = key.length, next = this.root; 

        for (let level = 0; level < length; level++) { 
            let character = key.charAt(level);

            if (next && next.children[character]) {
                next = next.children[character];
                continue;
            }
            return false;
        }

        return next && next.endOfWord;
    } 
}

function TrieNode() {
    this.children = {};
    this.endOfWord = false; 
}

使用上面的简单实现，您可以创建 Trie 实例并插入您想要的所有单词：

const trie = new Trie();
trie.insert("hello");
trie.insert("hi");
trie.insert("help");
trie.insert("helpful");
... more words

例如，使用 Node.js 您可以：

从源文件中读取所有需要的单词。
对于每个单词，使用 insert 方法将其插入 trie 结构。
通过以下方式从对象生成 JSON：JSON.stringify(trie)。
将其保存到一个文件：trie.js 稍后可以在您的页面上使用。

结果 js 上述单词的文件应如下所示：

{
   "root":{
      "children":{
         "h":{
            "children":{
               "e":{
                  "children":{
                     "l":{
                        "children":{
                           "l":{
                              "children":{
                                 "o":{
                                    "children":{
                                       
                                    },
                                    "endOfWord":true
                                 }
                              },
                              "endOfWord":false
                           },
                           "p":{
                              "children":{
                                 "f":{
                                    "children":{
                                       "u":{
                                          "children":{
                                             "l":{
                                                "children":{
                                                   
                                                },
                                                "endOfWord":true
                                             }
                                          },
                                          "endOfWord":false
                                       }
                                    },
                                    "endOfWord":false
                                 }
                              },
                              "endOfWord":true
                           }
                        },
                        "endOfWord":false
                     }
                  },
                  "endOfWord":false
               },
               "i":{
                  "children":{
                     
                  },
                  "endOfWord":true
               }
            },
            "endOfWord":false
         }
      },
      "endOfWord":false
   }
}

要创建一个有效的 JS 文件，您需要在开头添加以下代码：const RAW_TRIE = 字符串，因此我们的文件看起来像：

const RAW_TRIE = {
   "root":{
      "children":{
         "h":{
          ...

您创建了一个原始 Trie 对象，您可以通过将此行添加到您的 HTML 或模板文件来将其包含到您的页面中：

<script src="www.your-domain.com/path/to/static/file/trie.js"></script>

加载此文件后，您应该可以访问 RAW_TRIE 对象。您可以将 prototype 设置为 Trie 并使用搜索方法：

const TRIE = Object.setPrototypeOf(RAW_TRIE, new Trie());
console.log("hello exists: " + TRIE.search("hello"));
console.log("hello1 does not exist: " + TRIE.search("hello1"));

这种方法允许您在服务器端创建包含您需要的所有单词的文件，客户端可以下载它并用作常规静态文件。

Note: above solution is an only one way how to do that and some (or all) steps can be improved or changed. It is not a final version which can be used without any changes on production. You can try to optimise it and make trie.js file as small as possible by changing TrieNode function or even removing it.

Answer 2

以下是如何通过扩展本机 Map 原型来创建 Trie：

class TrieNode extends Map {
    add(word) {
        if (!word.length) return super.set("end", true);
        let child = this.get(word[0]);
        if (!child) this.set(word[0], child = new TrieNode);
        child.add(word.slice(1));
        return this; // optional: to allow chaining
    }
    has(word) {
        if (!word.length) return super.has("end");
        let child = this.get(word[0]);
        return !!child && child.has(word.slice(1));
    }
    * [Symbol.iterator]() {
        for (let [letter, child] of super.entries()) {
            if (letter === "end") yield ""
            else for (let word of child) yield letter + word;
        }
    }
}

// Demo
let trie = new TrieNode;
// Insert all words
for (let word of ["so", "some", "somebody", "someone", "something", "son"]) {
    trie.add(word);
}
// For a series of strings, check whether they are in the Trie
for (let word of Array.from("somethings", (_, i) => "somethings".slice(0, i))) {
    console.log(`"${word}" => ${trie.has(word)}`);
}
// List all words that are in the Trie
for (let word of trie) console.log(word);

运行时 Trie 数据结构生成与存储和读取文件方法

Runtime Trie data structure generation vs storing & reading to a file approach

javascript

json

trie

hierarchical-data

jackson