Python: Procurando frases com listas invertidas

Procurando por “Java”, temos esse resultado:

Legal! Conseguimos pegar todas os tópicos que contém a palavra Java, mas qual o problema do algoritmo que implementamos?

A complexidade do algoritmo

O algoritmo passa por todos os itens da lista para fazer a busca pela palavra, ele faz uma busca linear. Ou seja, se a lista tiver 5 elementos, ele passará pelos 5, se tiver 20 pelos 20, se tiver um milhão, vai passar por todos os itens, ufa… O tempo que nosso algoritmo leva para percorrer depende do número de itens na lista. 5, 10, 15, até **N **itens.

Logo, falamos que esse algoritmo tem complexidade O(n). De fato, é possível que todos os itens na lista tenham a palavra que estamos procurando, mas o que aconteceria se apenas o primeiro item tiver a palavra? Mesmo assim, teremos que percorrer todos os outros itens, apesar deles não terem o que procuramos.

Pensando em performance, esse algoritmo não é tão bom. Estamos em um contexto web no fórum da Alura. Se a busca demorar muito, afeta a experiência do usuário. Como podemos criar um algoritmo que consiga descobrir quais itens da lista tem a palavra que buscamos sem afetar muito a performance?

O poder dos hashes

No caso, estamos utilizando uma lista para guardar nossos tópicos. Outra estrutura que podemos utilizar são os conjuntos, ou sets. Quando estudamos estruturas de dados, uma das primeiras coisas que sabemos sobre eles é que eles guardam apenas uma ocorrência do item que ele guarda. Ou seja, se declararmos um conjunto dessa forma:

Quantos itens aparecerão quando pedirmos para imprimí-lo?

Só aparecem seis itens. Essa é uma das primeiras coisas que aprendemos, mas outra coisa muito interessante sobre conjuntos é que buscar itens fica muito mais rápido do que buscar itens em uma lista. Mas por que isso acontece? Para armazenar os itens, os conjuntos fazem uso de uma função especial, chamada de função hash.

A função hash é um algoritmo que pega o item que estamos buscando, ou inserindo no conjunto, e gera uma representação única para ele. Por exemplo, vamos pegar os números que usamos. A função hash do número pode ser o próprio número. Isso porque cada número é único no universo. O número 1 é o número 1. Só o número 1 pode ser o número 1. Se ele for outra coisa, não é mais o número 1, é outro número.

Neste caso, a função hash devolveria o próprio número que estamos buscando. No nosso exemplo de buscarmos palavras. Uma função hash que poderíamos utilizar é pegar a primeira letra da palavra. Por exemplo, Java retornaria J, Python P, JavaScript J também.

A partir dessa letra, podemos ter formas mais eficientes de buscar as palavras nos itens. Claro, nossos exemplos são bem simples, algoritmos de hash podem ser, e são, mais complexos que isso. Baseados em diferentes cálculos matemáticos para realizar o hash.

Estruturas de dados que utilizam hashes são, em geral, mais rápidas de fazer buscas do que estruturas que não utilizam. No nosso caso, temos várias frases. Quando alguém buscar uma palavra, temos que retornar os tópicos que contém aquela palavra. E se utilizarmos a palavra dos tópicos como o item em uma função hash?

Invertendo a lista

Em uma lista temos a seguinte estrutura: Falamos que na posição 0 está o item 'Como começar a programar?'.

E se invertemos esse modelo, isto é, falamos que a palavra é a posição e o item relacionado a essa palavra é uma lista com as posições dos tópicos na lista original? Por exemplo, para a palavra programar temos a uma lista com o item [0].

Já para a palavra Java temos uma lista com esses itens [4, 5, 6]. Dessa forma, podemos obter de um modo muito mais rápido os tópicos que estamos procurando, tudo isso utilizando o poder que os hashes dão para gente. Mas teremos que implementar essa função de hash na mão?

No Python, assim como na maioria das linguagens de programação, existem os dicionários, também conhecidos como mapas ou arrays associativos. Mapas são estruturas chave e valor. A chave é um item que passou por uma função de hash, logo, só podemos ter uma única ocorrência da chave no mapa. Logo, podemos ter um dicionário onde a chave são as palavras que existem nos tópicos, enquanto o valor seria uma lista com os índices do tópico na lista. No Python, uma das formas de criar o dicionários é dessa forma:

Os dicionários também utilizam de chaves ({ }) para serem criados, porém, diferente desses podemos passar as chaves e valores na hora de sua criação. O próximo passo é percorrer os tópicos na lista, como precisamos pegar o índice de cada tópico na lista, podemos utilizar a função enumerate().

Esta função construtora nos devolve um objeto enumerate onde o primeiro elemento é o índice e o segundo o valor, no nosso caso o tópico:

Agora, basta percorrermos as palavras do tópico. Para isso, temos que quebrar o texto nos espaços (split()) e checar se aquela palavra já existe no dicionário, se não existir, adicionamos nessa chave uma lista com o índice, se já existir, apenas acrescentamos à lista o índice do novo tópico:

Você pode estar se perguntando, se saímos de um loop para dois, a complexidade do algoritmo não aumentou também? De fato isso ocorreu. No nosso caso, para cada item na lista (N) percorremos suas palavras (N).

Ou seja, temos O(N * N) de complexidade, ou O(N^2). Neste caso, isso ocorreu pois estamos montando o dicionário. Contudo, nos próximos tópicos, basta pegarmos a posição na lista (índice) que ele foi alocado e iterar sobre suas palavras adicionando elas no dicionário. Com o dicionário agora, podemos fazer uma busca assim:

Temos apenas os índices dos tópicos que contém a palavra que buscamos. Basta pegarmos esses índices e buscarmos nos tópicos:

Buscando palavras Esse método que utilizamos para buscar as palavras é chamado de lista invertida, ou lista de index invertido (inverted index). Ele é um algoritmo muito utilizado para fazer buscas de palavras, isso porque ele é um algoritmo muito rápido.

Operação que envolvem dicionários tem complexidade de O(1). Fora isso, quando nos é devolvido uma lista com os índices dos tópicos, sabemos que aquele tópico contém a palavra que buscamos, não é necessário ficar checando palavra por palavra em todos os tópicos.

Esse algoritmo é muito utilizado em motores de busca, como o Google, ou então em ferramentas como o ElasticSearch. Nosso algoritmo no texto ficou bem simples. É possível aplicar transformações nas palavras como: passar todas as palavras para letra maiúscula ou minúscula, tirar acentos, plurais, eliminar palavras comuns, como artigos e pronomes também conhecido como stopwords tudo isso a fim de otimizar o algoritmo.

Aqui na Alura temos uma formação de aprendizado de máquina que mostra como fazer algumas dessas transformações.