Em cenários como fóruns e salas de bate -papo, para garantir a experiência do usuário, geralmente precisamos bloquear muitas palavras ruins. Para pesquisa de palavra -chave única, é naturalmente mais eficiente nos métodos indexos e regulares. No entanto, se houver muitas palavras -chave, se você ligar repetidamente com as palavras ou palavras regulares para corresponder ao texto completo, o consumo de desempenho será muito alto. Como a sequência de destino é geralmente grande em tamanho, é necessário garantir que o resultado seja obtido em uma travessia. Com base nessas necessidades, é fácil pensar em maneiras de combinar cada personagem em todo o texto em sequência. Por exemplo, para este texto: "Mike Jordan havia dito" apenas faça isso ", então Mark tem sido um codificador". Se nossa palavra -chave for "Mike" e "Mark", você pode atravessar toda a frase. Quando você encontrar "M", veja se você pode combinar "i" ou "a". Se você puder corresponder até o final, encontrará uma palavra -chave com sucesso; caso contrário, continuará atravessando. Então a estrutura das palavras -chave deve ser assim:
Var Keywords = {m: {i: {k: {e: {end: true}}}}, a: {r: {k: {end: true}}}}}Pelo exposto, podemos ver que esses dados são uma estrutura de árvore e ainda é demorado criar uma estrutura de árvore com base no grupo de palavras-chave, enquanto as palavras-chave já são fornecidas, para que você possa criar essa estrutura de dados com antecedência antes de corresponder. O código é o seguinte:
função BuildTree (Palavras -chave) {var Tblcur = {}, chave, str_key, comprimento, j, i; var tblroot = tblcur; for (j = keywords.length - 1; j> = 0; j - = 1) {str_key = palavras -chave [j]; Comprimento = str_key.length; for (i = 0; i <comprimento; i += 1) {key = str_key.charat (i); if (tblcur.hasownProperty (key)) {tblcur = tblcur [key]; } else {tblcur = tblcur [key] = {}; }} tblcur.end = true; // a última palavra -chave tblcur = tblroot; } retornar tblroot;}Este código usa uma instrução contínua: tblcur = tblcur [key] = {}. A ordem de execução aqui é a ordem de execução das declarações. Como o nível de operação de [] é maior que =, a primeira coisa é criar um atributo -chave no objeto TBLCUR. Combinado com tblroot = tblcur = {}, a ordem de execução é:
var tblroot = tblcur = {}; tblroot = tblcur; tblcur ['key'] = indefinido; // agora tblroot = {key: indefinido} tblcur ['key'] = {}; tblcur = tblcur ['key'];Através do código acima, os dados de consulta necessários são construídos. Vamos dar uma olhada no método de escrita da interface de consulta.
Para cada palavra da sequência de destino, começamos a partir da parte superior dessas palavras -chave. Primeiro, palavras -chave [a]. Se houver, veja a palavra -chave [a] [b]. Se a última palavra -chave [a] [b]… [x] = true, significa que a correspondência será bem -sucedida. Se a palavra -chave [a] [b]… [x] = indefinida, a correspondência será reiniciada a partir da próxima posição.
função pesquisa (content) {var tblcur, p_star = 0, n = content.length, p_end, corresponde, // se deve encontrar um match_key, match_str, arrmatch = [], // armazenamento o resultado arlength = 0; // o índice de comprimento de arrMatch while (p_star <n) {tblcur = tblroot; // rastreando de volta à raiz p_end = p_star; match_str = ""; Match = false; do {match_key = content.charat (p_end); if (! (tblcur = tblcur [match_key])) {// o final desta correspondência p_star += 1; quebrar; } else {match_str += match_key; } p_end += 1; if (tblcur.end) // se deve corresponder à cauda {match = true; }} while (true); if (match) {// MAXIMUM MACH ARRMACT [ARRLENGE] = {KEY: MATCH_STR, BEGIN: P_STAR - 1, END: P_END}; ArrLength += 1; p_star = p_end; }} retorna arrmatch;}O acima é o núcleo de todo o sistema de correspondência de palavras -chave. Aqui usamos muito bem os recursos do idioma do JS, e a eficiência é muito alta. Usei um "Soushen Ji" de 500.000 palavras para testá-lo e encontrei os 300 idiomáticos. O efeito correspondente é de cerca de 1 segundo. É importante ressaltar que o texto de destino é percorrido de uma só vez, a duração do texto de destino tem pouco efeito no tempo de consulta. O número de palavras -chave com maior impacto no tempo de consulta é o número de palavras -chave. Cada palavra no texto de destino atravessa as palavras -chave, por isso tem um certo impacto na consulta.
Análise simples
Eu acho que você está se perguntando quando leu o artigo acima. Você pode atravessar todas as palavras -chave para cada palavra. Mesmo que algumas palavras-chave sejam parcialmente as mesmas, é bastante demorado atravessá-las completamente. No entanto, as propriedades dos objetos em JS são construídas usando uma tabela de hash. Os dados dessa estrutura são muito diferentes da travessia simples da matriz, e a eficiência é muito maior que a da travessia de matriz baseada em pedidos. Alguns alunos podem não estar familiarizados com as estruturas de dados, por isso falarei brevemente sobre o conteúdo relevante da tabela de hash.
Primeiro, vamos dar uma olhada no armazenamento de dados.
O armazenamento de dados na memória consiste em duas partes, uma é o valor e o outro é o endereço. Pense na memória como um dicionário de Xinhua, a explicação da palavra é o valor e o diretório é o endereço. O dicionário é classificado por Pinyin, por exemplo, "Ni" com a mesma pronúncia é organizado na mesma peça, ou seja, a matriz é organizada em uma área de memória. Essa estrutura é uma matriz, você pode especificar "Ni" número 1 e 10 para acessá -la. O diagrama de estrutura é o seguinte:
A vantagem das matrizes é que elas são simples de atravessar e podem acessar diretamente os dados correspondentes por meio de subscritos. Mas é muito difícil adicionar ou excluir um determinado item. Por exemplo, se você deseja excluir o item 6, os dados após o item 5 devem ser movidos em frente por uma posição. Se você deseja excluir o primeiro bit, toda a matriz precisa ser movida, o que consome muito.
Para resolver o problema de adição e exclusão de matriz, as listas vinculadas aparecem. Se dividirmos o valor em duas partes, a parte será usada para armazenar o valor original e a outra parte é usada para armazenar um endereço, que aponta para outra mesma estrutura e assim por diante, forme uma lista vinculada. A estrutura é a seguinte:
Pode ser visto claramente na figura acima que adicionar e excluir a lista vinculada é muito simples. Basta reescrever o item de destino e o próximo item do item anterior e ele será concluído. No entanto, é muito difícil consultar o valor de um item. Você deve atravessá -lo, por sua vez, acessar o local de destino.
Para integrar as vantagens dessas duas estruturas, você deve ter pensado na seguinte estrutura.
Essa estrutura de dados é uma estrutura de tabela de hash. O endereço do cabeçalho da lista vinculado é armazenado na matriz e uma tabela de dados bidimensional pode ser formada. Quanto à forma como os dados são distribuídos, este é um algoritmo de hash, e uma tradução regular deve ser um algoritmo de hash. Embora existam muitos tipos de algoritmos, em princípio, eles resolvem a chave através de uma função e, em seguida, colocam os dados de acordo com os resultados obtidos da solução. Em outras palavras, é formado um mapeamento entre a chave e o endereço real; portanto, neste momento, não acessamos mais a matriz subscrevendo a matriz ou simplesmente atravessando -a, mas localizamos os dados pela função inversa da função de hash. O objeto em JS é uma estrutura de hash. Por exemplo, definimos um OBJ. Obj.name através do hash, e sua posição na memória pode ser 90 na figura acima. Quando queremos operar obj.name, a camada subjacente nos ajudará automaticamente a localizar a posição de 90 através do algoritmo de hash, o que significa que começamos diretamente a procurar a lista vinculada dos 12 itens da matriz, em vez de percorrer todo o bloco de memória de 0.
Defina um objeto obj {key: value} em js. A chave é convertida em uma string e depois hash para obter um endereço de memória e, em seguida, colocar o valor nela. Isso nos permite entender por que podemos adicionar e excluir atributos à vontade e por que também podemos atribuir atributos às matrizes no JS, e não há a chamada matriz transfronteiriça.
Em situações em que o volume de dados é grande, a tabela de hash tem uma vantagem muito óbvia, porque reduz muitos cálculos desnecessários através do algoritmo de hash. A chamada otimização de desempenho é realmente tornar os computadores menos computadores; A maior otimização é não calcular!
Otimização de algoritmos
Agora que você entende a implementação subjacente do algoritmo, considere otimizar o algoritmo em retrospecto. No entanto, antes de otimizar, você deve enfatizar uma coisa: não busque cegamente o desempenho! Por exemplo, neste caso, podemos corresponder a 5.000 palavras no máximo, portanto, o algoritmo existente é suficiente e todas as otimizações são desnecessárias. A razão pela qual ainda falo sobre otimização é melhorar minha compreensão do algoritmo e do programa, em vez de realmente fazer a otimização de 1MS.
Descobrimos que nenhuma de nossas palavras -chave tem uma única palavra, por isso seria um desperdício para atravessarmos palavras -chave de acordo com a unidade de uma palavra. A otimização aqui é pré-estatística o comprimento máximo e mínimo da palavra-chave e pesquisar nas unidades do comprimento mínimo de cada vez. Por exemplo, a palavra -chave no meu caso de teste é um idioma, e o mais curto é de 4 caracteres; portanto, toda vez que eu combino, combino 4 caracteres. Se eu acertar, continue pesquisando em profundidade para encontrar o comprimento máximo. Em outras palavras, quando construímos a árvore pela primeira vez, ela é construída pela primeira vez com o comprimento mínimo e depois é adicionado literalmente.
Um cálculo simples é feito. De acordo com o nosso caso de teste, para 300 expressões idiomáticas, precisamos comparar apenas uma palavra uma vez e, para uma consulta de palavra única, precisamos comparar 4 vezes e cada comparação que temos que acessar nossa estrutura de árvores, que é o consumo de desempenho evitável. Mais importante, a comparação aqui não é uma comparação de string. Nossas palavras -chave aqui existem como chaves, e o efeito é o mesmo que a chave no OBJ, que é hash a chave e depois acessa o endereço correspondente! Portanto, não se preocupe com a diferença entre comparar uma palavra e comparar quatro palavras. Não comparamos strings!
Isso se trata de corresponder várias palavras -chave. Não vou postar a versão otimizada do código porque geralmente não está disponível.