Olá meus amigos nerds! Hoje vamos ver que o conhecimento que adquirimos ao brincar em maratonas de programação pode nos ser útil no mundo real. Vou compartilhar com vocês um problema desafiador que tive que resolver essa semana no trabalho.
Essa semana estava trabalhando em um modelo para prever se um candidato seria uma boa indicação para uma dada vaga. Feliz ou infelizmente, o dataset que eu tinha a minha disposição é bem grande, mas a maior parte da informação contida nele está em forma de texto.
Parte da arte de se criar bons modelos de machine learning está em
escolher e usar as informações certas ao construir o modelo. Features textuais costumam conter bastante informação, entretanto extrair essa informação costuma ser problemático, já que as máquinas gostam de lidar com números.
Em particular, no modelo que eu estava criando, eu gostaria de usar as skills (descrições curtas de habilidades do candidato) presentes nos currículos. E, para minha felicidade, eu tinha a minha disposição uma tabela contendo tal informação.
Infelizmente eu não tinha essa mesma informação para as vagas, então decidi extraí-la da descrição das mesmas. Aí começa o problema.
Dada a descrição textual de uma vaga e uma tabela contendo skills (ex: mineração de dados, vendas, etc) eu gostaria de saber quais são as skills exigidas pela vaga.
O problema
Ué mas não é só dar um .find() das skills no texto e pronto? Onde está o problema desafiador? Aqui no blog já resolvemos alguns problemas de casamento de padrões mais difíceis que esse!
Bem meus amigos, o problema está na escala! Minha tabela de skills continha algo em torno de 1 milhão de registros. Além disso, eu também tinha alguns milhões de vagas o que torna a solução de força bruta inaplicável.
Problemas envolvendo escala costumam ser interessantes e esse não é diferente. Vamos ver como, mesmo algo que é simples quando lidamos com pequenos volume de dados, pode se tornar desafiador quando o tamanho dos dados realmente importa.
Para você ter uma ideia, a biblioteca de regex do python levou um ou dois minutos para compilar toda a tabela em padrões da forma p1|p2|...|pn. Além disso, o automato gerado por ela levava em torno de 1s para extrair os padrões de apenas uma vaga. 1s é o mesmo que infinito, se considerarmos que o SLA (tempo de resposta acordado) para a maioria das APIs que eu trabalho gira em torno de 200ms. Só para vocês terem uma ideia, usando-se uma máquina moderna levaríamos cerca de 10 dias só para extrair as skills de 1M vagas.
Ou seja, nosso problema é grande o suficiente para que a biblioteca padrão (consideravelmente otimizada) de uma linguagem moderna não seja suficiente.
Solução
Se todas as nossas skills fossem compostas apenas de uma palavra a solução de complexidade ótima (O(# palavras na descrição das vagas)) seria indexar nossas skills em uma tabela hash. Assim, para cada palavra na descrição da vaga, poderíamos verificar se ela esta presente no hash ou não.
O nosso problema é que as skills não são formadas apenas por uma palavra. Para contorná-lo basta criar uma árvore com as palavras das skills, onde cada nó da árvore representa uma palavra e existe uma aresta ligando dois nós se uma skill possui as duas palavras em sequência. Em outras palavras, a ideia para resolver esse problema é uma árvore de prefixos. Cada nó da árvore pode ter vários filhos, que podem ser mantidos em um hash para otimizar a busca.
Para buscar pelas skills então basta tokenizar o texto da vaga e para cada token ir andando com ele na árvore de prefixos de skills, verificando se aquele token gera ou não um match.
Implementação
Acho que essa é a primeira vez que uso uma de minhas linguagens preferidas para resolver um problema por aqui. O código Python abaixo implementa a ideia da árvore de prefixos.
