A auto-complete leve ActionScript exemplo com uma trie

Este artigo foi escrito originalmente em Inglês. Textos em outros idiomas foram fornecidos via tradução automática.


Auto-completar funcionalidade é amplamente utilizado através da internet e aplicativos móveis. Um monte de sites e aplicativos tentar completar a sua entrada, logo que você começa a digitar. Neste post, Gostaria de introduzir um simples ActionScript solução de auto-completar usando estrutura de dados trie.

Uma trie é uma árvore ordenada estrutura de dados que é usado para armazenar uma matriz associativa. Todos os descendentes de um nó têm um prefixo comum da seqüência associada a esse nó, ea raiz é associado com a string vazia. A partir do nó raiz, você pode verificar se uma palavra existe na trie facilmente por ponteiros seguintes correspondentes às letras na palavra-alvo. Trie é uma conhecida estrutura de dados em ciência da computação; você pode encontrar informações detalhadas sobre trie através Wikipedia.

Aqui está uma aplicação simples em ActionScript trie:

/**
* Uma estrutura de dados simples para armazenar e procurar palavras.
* @ See http://en.wikipedia.org / wiki / Trie para obter detalhes adicionais.
*/

public class Trie {
private var _rootKeys:Array;
public function Trie():void {
_rootKeys=[];
}

/**
* Retornar uma lista de palavras que têm o prefixo dado.
*/

public function get(prefix:String):Array {
var results:Array=[];
var letter:String=prefix.substr(0,1);
var root:TrieNode=_rootKeys[letter];
if (root) {
getWordList(prefix, 1, root, results);
}
return results;
}

/**
* Adicionar uma palavra para o objeto que pode ser comparada como um prefixo.
*/

public function add(word:String):void {
var letter:String=word.substr(0,1);
var root:TrieNode=_rootKeys[letter];


if (!root) {
root=createNode(letter);
_rootKeys[letter]=root;
}
insertWord(word, 1, root);
}


private function traverse(root:TrieNode, results:Array, prefix:String):void {
if(root.children) {
for each( var c:TrieNode in root.children ) {
var node:TrieNode = c as TrieNode;
if( node.word ) {
results.push( prefix + node.value);
}
traverse(node, results, prefix+node.value );
}
}
}


private function getWordList(prefix:String,
position:uint,
root:TrieNode,
results:Array):void {
var letter:String=prefix.substr(position,1);
var child:TrieNode=root.children[letter];
if (!letter || !child) {
return;
}


if ( position<(prefix.length-1) ) {
getWordList(prefix, ++position, child, results);
}else {
if (!child.word) {
traverse( child, results, prefix);
}
}

}


private function insertWord(word:String,
position:uint,
root:TrieNode):void {
var letter:String=word.substr(position,1);
if (position==word.length || !letter) {
return;
}


var child:TrieNode=root.children[letter];
if (! child) {
child=createNode(letter);
root.children[letter]=child;
}


if (position==word.length-1) {
child.word=true;
} else {
insertWord(word, ++position, child);
}
}


private function createNode(letter:String):TrieNode {
return new TrieNode(letter,false);
}
}

Deixe uma resposta