在ActionScript 3中，搜索一个非常长的单词列表以查找匹配项的最快方法是什么？

Question

我有一个单词列表（整个英语词典）。

在一个单词匹配游戏中，当玩家移动棋子时，我需要检查整个词典，以查看玩家所构成的单词是否存在于词典中。我需要尽快完成这个任务。简单地遍历整个词典太慢了。

在AS3中，最快的算法是什么，可以用什么数据类型进行搜索？（例如数组、对象、字典等）

- Nuthman

Answer 1

我会首先使用一个对象，它是一个哈希表（至少在存储方面是这样的）。

因此，对于列表中的每个单词，在您的字典对象中创建一个条目并将 true 作为其值存储。

然后，只需检查给定的单词是否为字典中的键即可知道用户选择的单词是否有效。

在这个简单的测试中，它运行得非常快（有 10,000,000 个条目）。

var dict:Object = {};
for(var i:int = 0; i < 10000000; i++) {
    dict[i] = true;
}
var btn:Sprite = new Sprite();
btn.graphics.beginFill(0xff0000);
btn.graphics.drawRect(0,0,50,50);
btn.graphics.endFill();
addChild(btn);
btn.addEventListener(MouseEvent.CLICK,checkWord);

var findIt:Boolean = true;
function checkWord(e:MouseEvent):void {
    var word:String;
    if(findIt) {
        word = "3752132";
    } else {
        word = "9123012456";
    }

    if(dict[word]) {
        trace(word + " found");
    } else {
        trace(word + " not found");
    }
    findIt = !findIt;
}

建立字典需要一些时间，但查找几乎是瞬间完成的。

唯一的注意事项是您需要考虑某些键，这些键将通过检查，但不一定是您单词列表的一部分。例如toString，prototype等单词。虽然只有很少量，但请记住这一点。

我建议您使用真实数据集尝试此方法。如果正常工作，则您有一个非常简单的解决方案。去喝一杯啤酒（或您喜欢的任何饮料）吧。

现在，如果以上内容在使用真实数据进行测试后并不能正常工作（请注意，我已经为简单起见使用数字字符串构建了列表），那么以下是我能想到的一些选项：

1）将第一个“dict”分成一组字典。因此，不要将所有单词都放在“dict”中，而是为以'a'开头的单词、以'b'开头的单词等设置一个字典。然后，在查找单词之前，检查第一个字符以知道在哪里查找它。

类似于：

var word:String     = "hello";
var dictKey:String  = word.charAt(0);
// actual check
if(dict[dictKey][word]) {
    trace("found");
} else {
    trace("not found");
}

你最终可以重新分区，如果必要的话。也就是说，让dict['a']指向另一组由前两个字符索引的字典。所以，你将有dict['a']['b'][wordToSearch]。这个想法有很多可能的变化（例如，你还必须想出一些应对两个字母单词的策略，比如“be”）。

2）尝试二分搜索。它的问题在于你需要预先对列表进行排序。你只需要做一次，因为从字典中删除单词是没有意义的。但如果有数百万个单词，这可能会相当耗费时间。

3）尝试来自开源库的一些花哨的数据结构。

http://sibirjak.com/blog/index.php/collections/as3commons-collections/

http://lab.polygonal.de/ds/

但是，正如我之前所说的那样，我会首先尝试最简单和简单的解决方案，并检查它是否适用于真实数据集。

添加

处理用于对象内置属性的关键字的简单方法：

var dict:Object = {};
var keywordsInDict:Array = [];

function buildDictionary():void {
    //  let's assume this is your original list, retrieved 
    //  from XML or other external means
    //  it contains "constructor", which should be dealt with
    //  separately, as it's a built-in prop of Object
    var sourceList:Array = ["hello","world","foo","bar","constructor"];
    var len:int = sourceList.length;
    var word:String;
    //  just a dummy vanilla object, to test if a word in the list 
    //  is already in use internally by Object
    var dummy:Object = {};

    for(var i:int = 0; i < len; i++) {
        //  also, lower-casing is a good idea
        //  do that when you check words as well
        word = sourceList[i].toLowerCase();
        if(!dummy[word]) {
            dict[i] = true;
        } else {
            //  it's a keyword, so store it separately
            keywordsInDict.push(word);
        }
    }
}

现在，只需在checkWords函数中添加一个内置道具的额外检查即可：

function checkWord(e:MouseEvent):void {
    var word:String;
    if(findIt) {
        word = "Constructor";
    } else {
        word = "asdfds";
    }
    word = word.toLowerCase();
    var dummy:Object = {};
    //  check first if the word is a built-in prop 
    if(dummy[word]) {
        //  if it is, check if that word was in the original list
        //  if it was present, we've stored it in keywordsInDict
        if(keywordsInDict.indexOf(word) != -1) {
            trace(word + " found");
        } else {
            trace(word + " not found");
        }
    // not a built-in prop, so just check if it's present in dict 
    } else {
        if(dict[word]) {
            trace(word + " found");
        } else {
            trace(word + " not found");
        }
    }
    findIt = !findIt;
}

- Juan Pablo Califano

---

这非常有帮助和详细。我会尝试一下，看看会发生什么！幸运的是，我的游戏最大单词长度为5个字母，因此它有助于显著减小字典的大小。谢谢！ - Nuthman

很棒的答案。通常最好按照简单的顺序尝试事情，并在使用真实数据时获得可接受的性能后停止。 - fenomas

Answer 2

这不是特定于ActionScript的，但Trie是一种适合存储单词的数据结构。

- Kobi