如果你的列表中有很多单词，为了缩小字典的大小，你可以使用
Patricia Trie。Patricia Trie是一种专门优化搜索字符串的树形结构。基本上，Trie中的每个节点都是一个单独的字母。例如：
var dictionary = {
'a': {
'': 1,
'a': {
'': 1,
'l': {
'': 1,
'ii': 1
},
'm': 1,
'ni': 1,
'r': {
'd': {
'vark': 1,
'wolf': 1
},
'on': {
'': 1,
'ic': 1
}
}
},
},
}
在上面的代码中，我使用空字符串 ''（实际上是有效的属性标识符！）来表示单词的结尾。
以下是如何实现搜索：
function isWord_internal(str, dic) {
var strlen, i, substr, substrlen;
strlen = str.length;
for(i = strlen; i > 0; i--) {
substr = str.slice(0, i);
substrlen = substr.length;
if(dic[substr]) {
if(dic[substr] === 1) {
if(substrlen === strlen) {
return true;
}
return false;
}
if(dic[substr][''] && substrlen === strlen) {
return true;
}
return isWord_internal(str.slice(i), dic[substr]);
}
}
return false;
}
function isWord(str) {
return isWord_internal(str, dictionary);
}
由于对象是哈希表 O(log n)，而算法与单词大小线性相关，因此您的性能应为 O(n log n)。
这也应该使您的列表大小保持不变，因为英语单词不是随机的，通常具有共同的子字符串（虽然您可能需要将其最小化）。
要转换您当前的字典，您可以使用此函数在内存中生成它：
function patriciafy_internal(str, pat) {
var i, substr, patkeys, patkeyslen, j, patkey, pos, portion;
for(i = str.length; i > 0; i--) {
substr = str.slice(0, i);
patkeys = Object.keys(pat);
patkeyslen = patkeys.length;
for(j = 0; j < patkeyslen; j++) {
patkey = patkeys[j];
pos = patkey.indexOf(substr);
if(pos !== -1) {
if(pat[patkey] !== 1) {
patriciafy_internal(str.slice(i), pat[patkey]);
} else {
portion = patkey.slice(0, pos + 1);
delete pat[patkey];
pat[portion] = {'': 1};
pat[portion][str.slice(1)] = 1;
}
return;
}
}
}
pat[str] = 1;
}
function patriciafy(dic) {
var pat, keys, keyslen, str, i;
pat = {};
keys = Object.keys(dic);
keyslen = keys.length;
for(i = 0; i < keyslen; i++) {
str = keys[i];
patriciafy_internal(str, pat);
}
return pat;
}
然后只需使用
JSON.stringify将其打印出来以供使用。
在我的机器上进行的一项测试，使用235,887个单词的字典（从
here中获取），表明Patricia树比单词的平面字典小了约三分之一，其中平面字典的格式为
{"name":1,"name2":1,...}。
这仍然很大，但明显小了很多。你可以通过将其存储在非JS格式中来节省相当大的空间，例如。
var dictionary = {
'a': {
'': 1,
'a': {
'': 1,
'l': {
'': 1,
'ii': 1
}
}
}
};
压缩后变成
// 57 characters
var dictionary={'a':{'':1,'a':{'':1,'l':{'':1,'ii':1}}}};
可以变成
// 17 characters - single @ represents ''
@a{@@a{@@l{@@i}}}
然后你将解析它。
=====
patricia树到@语法：
function patToAt_internal(pat) {
var keys, i, s = "", key;
s += "{";
keys = Object.keys(pat);
for(i = 0; i < keys.length; i++) {
key = keys[i];
s += "@";
s += key;
if(pat[key] !== 1) {
s += "{" + patToAt_internal(pat[key]) + "}";
}
}
s += "}";
return s;
}
function patToAt(pat) {
return patToAt_internal(pat);
}
@-语法转换为 Patricia 树：
function atToPat_internal(at, pos) {
var s = "", result, ff = true, ch;
s += "{";
pos++;
while((ch = at.charAt(pos)) !== "}") {
pos++;
if(!ff) s += ",";
else ff = false;
s += '"';
while((ch = at.charAt(pos)) !== "@" && ch !== "{" && ch !== "}") {
s += ch;
pos++;
}
s += '":';
if(ch === "{") {
result = atToPat_internal(at, pos);
s += result.s;
pos = result.pos + 1;
} else {
s += "1";
}
}
s += "}";
return {pos: pos, s: s};
}
function atToPat(at) {
return JSON.parse(atToPat_internal(at, 0).s);
}
使用@语法，总大小缩小到原始平面字典的三分之一：
总之...
使用这种方法，你需要最初（仅一次）通过执行以下步骤来构建 @-tree。
var dictionary = { ... } // your words here
// usually you can get all of the log if you triple click, or just output it into a textarea
console.log(patToAt(patriciafy(dictionary)));
然后，一旦你完成了这个步骤，在你的页面上，你可以执行以下操作：
var dictionary = atToPat("...");
isWord('apple');
