Eu tenho um banco de dados de cerca de 200 documentos que são ngrams que eu extraí. Quero encontrar o documento no meu banco de dados que seja mais semelhante a um documento de consulta. Em outras palavras, desejo encontrar o documento no banco de dados que compartilhe o maior número de ngrams com o documento de consulta. No momento, posso analisar cada uma delas e compará-las uma a uma, mas isso levará tempo de O (N) e será caro se N for muito grande. Fiquei me perguntando se existem estruturas ou métodos de dados eficientes na busca eficiente de similaridades. obrigado
7
Respostas:
Você pode usar um vetorizador de hash em seus documentos. O resultado será uma lista de vetores. Em seguida, vectorize seus ngrams da mesma maneira e calcule a projeção desse novo vetor nos antigos. Isso é equivalente à junção do banco de dados em um índice, mas pode ter menos sobrecarga.
fonte
A estrutura de dados normalmente usa é um índice invertido (por exemplo, em bancos de dados).
Observe que combinar todos os ngram é uma boa heurística, mas você pode querer melhorá-la.
Levando em conta a probabilidade de cada termo e a derivada, são as direções das quais você pode se beneficiar.
fonte
mesa
ngram
docID
PK (chave primária) ngram, docID
dependendo do banco de dados pode mudar um pouco, mas isso é para TSQL
x é o documento que você está correspondendo
A junção está em um índice (PK), portanto, isso é muito rápido. Faço isso em um milhão de documentos em apenas alguns segundos (com condições mais avançadas).
Isso favorecerá documentos maiores, mas foi o que você pediu.
A pergunta parece estar mudando
fonte
Do seu esclarecimento -
Você faria bem em fazer algo um pouco mais estruturado e colocar os dados em um banco de dados relacional. Isso permitiria que você fizesse análises muito mais detalhadas com mais facilidade e rapidez.
Eu acho que quando você diz "ngram", você quer dizer "1gram". Você pode estender a análise para incluir 2 gramas, 3 gramas, etc., se desejar.
Eu teria uma estrutura de tabela que se parece com isso -
1Grams
ID
Value
Docs
ID
DocTitle
DocAuthor
etc.
Docs1Grams
1GramID
DocID
1GramCount
Portanto, no registro da tabela Docs1Grams, quando 1GramID aponta para o 1gram "the" e o DocID aponta para o documento "War and Peace", o 1GramCount retém o número de vezes que o 1gram "the" aparece em War and Peace.
Se o DocID de 'Guerra e paz "for 1 e o DocId de" Senhor dos anéis "for 2, calcule a pontuação de similaridade de 1 grama para esses dois documentos, você faria esta consulta -
Ao generalizar e expandir a consulta, isso pode ser facilmente alterado para selecionar automaticamente a pontuação / contagem mais alta, comparando o documento escolhido com todos os outros.
Ao modificar / expandir a
D1.1GramCount > 0 and D2.1GramCount > 0
parte da consulta, você pode facilmente tornar a comparação mais sofisticada, por exemplo, adicionando 2Grams, 3Grams, etc. ou modificando a correspondência simples para pontuar de acordo com a porcentagem de correspondência por ngram.Portanto, se o documento do assunto tiver 0,0009% dos 1 gramas sendo "o", o documento 1 tiver 0,001% e o documento 2 tiver 0,0015%, o documento 1 terá uma pontuação mais alta no "the" porque o módulo da diferença (ou qualquer outra medida que você escolher) usar) é menor.
fonte
Se você deseja verificar a presença de n gramas no documento, precisará converter o documento de consulta também em n gramas. Para fazer isso, você pode usar o vetorizador TFIDF.
Para explicar o código acima:
word_tokenize : esta função converte o texto em tokens de string, mas você precisará limpar os dados adequadamente.
ngram_range : define o número de ngrams necessários. Nesse caso, serão necessárias 1 e 2 palavras.
max_features : limita o total não. de recursos. Eu recomendo usá-lo se você quiser tokenizar alguns documentos como não. de recursos é muito alto (na ordem de 10 ^ 6).
Agora, depois de ajustar o modelo, os recursos são armazenados no "vect". Você pode visualizá-los usando:
Agora que você tem os gramas do seu documento de consulta armazenados em um conjunto, é possível executar operações de conjunto muito mais rápidas em comparação com os loops. Mesmo que a duração de cada conjunto seja da ordem de 10 ^ 5, você obterá resultados em segundos. Eu recomendo tentar conjuntos em python.
Por fim, você obterá todas as palavras-chave correspondentes em "matching_keys".
fonte