Melhor maneira de procurar um documento semelhante, dado o ngram

7

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

okebz
fonte
Como você encontrará mais ngrams se não os calcular? Compare um por um? Essa é uma consulta simples e simples.
Paparazzo
Os ngrams para os documentos são todos calculados, assim como a consulta. O problema é que agora quero ver qual documento no banco de dados é mais semelhante à consulta. Ou melhor, obtenha os 10 documentos mais semelhantes à consulta, com base em seus ngrams.
okebz
A questão declarada é que o ngram foi extraído. Agora você está dizendo que eles são calculados. Documento de consulta para mim é documento. A resposta é tão boa quanto a pergunta. Qual banco de dados? A sintaxe varia.
Paparazzo
Eu quis dizer extraído. De qualquer forma, os ngrams são obtidos de cada documento, então estou apenas trabalhando com os próprios ngrams. Você tem um banco de dados de ngrams que representam cada documento no banco de dados. Você tem um documento de consulta onde deseja encontrar, digamos os 10 principais documentos que parecem mais semelhantes à sua consulta. Pelo banco de dados, vamos apenas dizer que não há uma lista enorme do modelo Ngram que representa o documento
okebz
E você tem uma resposta minha. Um banco de dados com design de tabela não declarado realmente não o reduz.
Paparazzo

Respostas:

3

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.

Diego
fonte
1

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.

DaL
fonte
1

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

select top(1) with ties *    
from 
(  select tm.docID, count(*) as count 
     from table td
     join table tm
       on tm.docID <> td.docID 
      and tm.ngram = td.ngram 
      and td.docID = x
    group by tm.docID 
) tt 
order by count desc

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

declare table @query (varchar ngram);
insert into @query values ('ng1'), ('ng2'), ('ng3');
select top(10) with ties *    
from 
(  select tm.docID, count(*) as count 
     from table td
     join @query
       on tm.ngram = @query.ngram
    group by tm.docID 
) tt 
order by count desc
paparazzo
fonte
1

Do seu esclarecimento -

Por banco de dados, digamos que exista uma lista enorme do modelo ngram que representa o documento

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 -

Select count(*) from Docs1Grams D1, Docs1Grams D2   
where D1.DocID = 1 and   
D2.DocID = 2 and   
D1.1GramID = D2.1GramID and   
D1.1GramCount > 0 and   
D2.1GramCount > 0   

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 > 0parte 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.

Brian Towers
fonte
1

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.

from nltk.tokenize import word_tokenize               
from sklearn.feature_extraction.text import TfidfVectorizer
vect = TfidfVectorizer(tokenizer=word_tokenize,ngram_range=(1,2), binary=True, max_features=10000)
TFIDF=vect.fit_transform(df_lvl0['processed_cv_data'])

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:

keywords=set(vect.get_feature_names())

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.

matching_keys = keywords.intersection(all_grams)   //all_grams is the set of your collected grams

Por fim, você obterá todas as palavras-chave correspondentes em "matching_keys".

Harsha Reddy
fonte