Aplicando Tries para padronizar inconsistência em textos utilizando Kotlin (Server-Side)

Trie (ou árvore de prefixo) é um ótimo exemplo de estrutura de dados que recebe menos crédito e publicidade do que deveria. Apesar de sua aplicação mais difundida ser na implementação de funcionalidades de “autocomplete”, quase um commodity na grande maioria das aplicações, está muito longe de ser a única.

Recentemente aqui no #Localizalabs utilizamos essa estrutura para padronizar a grande variabilidade de nomes dados internamente para alguns dos nossos locais de operação — evitando possíveis confusões por parte dos usuários de um dos nossos aplicativos.

Primeiro, para quem não tem tanta familiaridade com o tema, farei uma breve introdução sobre o que são as árvores de prefixo. Se você já está careca de saber, pule direto para o problema e a implementação.

Trie (ou preffix tree, ou digital tree)

De forma bastante objetiva, as Tries são árvores onde cada nó (exceto o raiz) é representado por uma cadeia de caracteres implementada por um lista preferencialmente encadeada, mas não há regra para isso — se trata apenas de maximizar a eficiência.

Visualmente (e talvez não tão óbvio), uma árvore de prefixo é isso aqui:

Representação visual de uma Trie com termos do dicionário Inglês

Para entendermos melhor, podemos desconsiderar os números associados a alguns dos nós. Isso porque existem variações para implementação de uma Trie e a representação de um final de termo (por assim dizer) pode tomar diversas formas. Nesse caso usou-se um número, mas poderia ser qualquer outra coisa, como veremos no caso aplicado por nós.

O importante é entender que os caracteres “t”, “A” e “i”, associados ao nó raiz e identificados pelas respectivas arestas, representam uma lista. Por conseguinte, o conjunto “o” e “e”, associado ao nó t (e, portanto, a posição 0 da lista “t”, “A” e “i”) também representa uma lista. Contudo, o nó “to” não possui listas descendentes. Isso porque essa árvore trata de termos presentes no dicionário da língua inglesa e, nesse dicionário, a junção “to” representa uma preposição. Voilà!

Em resumo, isso é suficiente para entendermos como essa estrutura (com algumas adaptações) foi utilizada no nosso caso. Então, vamos ao problema.

O Problema

Aqui no #Localizalabs morremos de orgulho de dizer quão grande nós somos. Porém, ser grande, como nós bem sabemos, tem lá seus custos (e suas oportunidades).

Após uma implementação importante em uma das nossas aplicações, identificamos que os nomes de alguns dos nossos locais de operação não estavam muito claros, levando a confusão por parte de alguns usuários.

A origem do problema se deu por algumas condições internas irrelevantes para o caso mas o fato é que alguns locais eram identificados assim: CM P Seg Recife; P Segur Recife; Ag Recife; Ag. C Recife; C M P Segur Recife.

Todos esses locais são locais reais, fazem parte da nossa base, compõem nossa operação, mas temos que convir que é, no mínimo, deselegante exibir uma listagem com esses nomes.

Desafio

A diversidade de nomenclaturas era bastante vasta, a quantidade de registros não era pequena e, como era parte de um processo de consolidação, a inclusão, remoção ou modificação dos locais exigiria que tivéssemos um controle granular de cada ajuste — ou que fosse realizado o ajuste manual, o que não era o caso.

Então, precisávamos pensar numa forma de ajustar que fosse perene, pudesse ser executada continuamente para manter o padrão mesmo que a base de referência mudasse, e fosse o mais eficiente possível tanto do ponto de vista de recursos quanto do tempo de execução, onerando o mínimo possível o processo de consolidação.

Tries to the Recue

Para alcançar os requisitos que precisávamos, optamos pelo uso de uma árvore de prefixos com uma implementação um pouco diferente, que permitisse que sua composição fosse baseada exclusivamente pelos nomes “errados”, permitindo sua comparação com cada um dos registros e, como complemento, utilizamos um Hashmap para armazenar as equivalências corretas no nome.

A Implementação contém as seguintes classes:

ClosestMatch: é a classe que utilizamos para armazenar a melhor correspondência encontrada dentro da árvore para uma dada palavra.

Node: são todos os nós da árvore. A raiz sempre possuirá value nulo; O atribute word é utilizado para identificar qual nó representa o fim de uma palavra; children representa a lista de filhos (arestas, no exemplo da imagem utilizada no início do post).

Trie: a implementação da própria árvore, que possui os dois métodos fundamentais insertIntoTrie e searchInTrie. O método searchInTrie possui uma variação da Trie tradicional, permitindo, a cada palavra, a identificação do ClosestMatch.

Para complementar, utilizamos uma Hashtable para associar os padrões “errados” aos corretos e implementamos uma função para ajustar esses nomes.

Agora, a parte mais fácil: montar a árvore com os erros encontrados e caminhar pelos nós procurando prefixos similares.

Resultado

Com a utilização dessa estrutura fomos capazes de resolver as inconsistências e melhorar a experiência do usuário acrescentando menos de 1s ao tempo total de execução dos scripts de consolidação. Executando o exemplo acima, em uma máquina convencional, conseguiríamos (hipoteticamente) renomear 1 milhão de resultados em pouco mais de 9s — não considerando o período para update em banco ou outras operações periféricas.

Uma importante parte dessa estratégia foi garantir que a altura da árvore fosse pequena o suficiente para ser navegada sem ônus ao sistema; garantindo uma execução eficiente mesmo para grande quantidade dados. Atenção: o fator que pode aumentar a complexidade está na quantidade de palavras pesquisadas e não no tamanho da árvore — que será constante para todas as palavras. Por isso concluimos que a complexidade de tempo para a árvore é: O(n)

Ex: se o pior caso de “erro” for “C M Post Seg” a recursão máxima será de 12 vezes (a altura da árvore); no melhor caso apenas uma execução.

É isso. Certamente existem tantas outras formas de resolver esse mesmo problema e a magia e a diversão da coisa é justamente essa.

Para terminar, por que você não aproveita o momento e tenta implementar um árvore para identificar palavras de um contexto específico para validar o conhecimento?

Boa sorte! ;-)