busca dinâmica e exibição

Question

Eu tenho uma grande carga de documentos, arquivos-texto, que eu quero procurar conteúdo relevante. Eu vi uma ferramenta de busca, não pode lembrar-se é onde, que implementou um método agradável como eu descrevo em meu exigência abaixo.

Minha exigência é a seguinte:

• Eu preciso de uma função de pesquisa optimizada: I fornecer essa função de pesquisa com uma lista (um ou mais) palavras parcialmente completos (ou completa), separados por espaços.
• A função, em seguida, encontra todos os documentos contendo palavras que começam ou igual à primeira palavra, em seguida, procurar estes documentos encontrados da mesma forma usando a segunda palavra, e assim por diante, no final do qual ele retorna uma lista contendo o real palavras encontradas ligada com os documentos (nome e localização) que os contenham, para a completar a lista de palavras.
• Os documentos devem conter todas as palavras da lista.
• Eu quero usar essa função para fazer uma pesquisa as-you-tipo para que eu possa exibir e atualizar os resultados em uma estrutura de árvore em tempo real.

Uma abordagem possível para uma solução que eu vim com é a seguinte: Eu criar um banco de dados (provavelmente usando mysql) com três tabelas: 'Documentos', 'palavras' e 'Word_docs'

.

• 'Documentos' terá (idDoc, nome, Location) de todos os documentos.
• 'Palavras' terá (idWord, Word), e ser uma lista de palavras originais de todos os documentos (uma palavra específica aparece apenas uma vez).
• 'Word_docs' terá (idWord, idDoc), e ser uma lista de id-combinações únicas para cada palavra e documento que aparece.

A função é então chamado com o conteúdo de uma caixa de edição em cada toque de tecla (exceto espaço):

• a string é tokenized
• (aqui minhas rodas girar um pouco): Estou certo de que uma única instrução SQL pode ser construído para retornar o conjunto de dados necessários: (actual_words, DOC_NAME, doc_location); (Eu não sou um número-quente com SQL), em alternativa uma sequência de chamadas para cada token e parse-out a não-repetição idDocs?
• este conjunto de dados (/ list / matriz) é então devolvido

A lista de conteúdo retornado é então exibida:

g .: chamado com: "seq sta bacalhau" exibe:

sequence - start - code - Counting Sequences [file://docs/sample/con_seq.txt]
         - stop - code - Counting Sequences [file://docs/sample/con_seq.txt]
sequential - statement - code - SQL intro [file://somewhere/sql_intro.doc]

(e-assim-on)

Esta é uma ótima maneira de fazê-lo? A função precisa ser rápido, ou deveria ser chamado somente quando um espaço é atingido? Deve oferecer palavra-conclusão? (Tenho as palavras do banco de dados) Pelo menos isso iria evitar chamadas inúteis para a função para palavras que não existem. Se palavra-conclusão: como teria que ser implementada

(Talvez SO também poderia usar esse tipo de pesquisa de solução para visitar os tags? (No canto superior direito da página principal))

Answer 1

O que você está falando é conhecido como um href="http://en.wikipedia.org/wiki/Inverted_index" rel="nofollow noreferrer"> lista de índice ou postagem invertido

Melhor, ao invés de tentar construí-lo, use uma implementação índice invertido existente. Ambos MySQL e recentes versões do PostgreSQL tem indexação de texto completo por padrão. Você também pode querer verificar para fora Lucene para uma solução independente. Há um monte de coisas a considerar em escrever um boa índice invertido, incluindo tokenização, decorrente, consultas de várias palavras, etc, etc, e uma solução pré-integrada vai fazer tudo isso para você.

Answer 2

A maneira mais rápida não é, certamente, usando um banco de dados em tudo, desde que se você fizer a busca manualmente com dados otimizados, você pode facilmente bater selecione o desempenho da pesquisa. A maneira mais rápida, assumindo que os documentos não mudam muito frequentemente, é a construção de arquivos de índice e usá-los para encontrar as palavras. O arquivo de índice é criado assim:

1. Encontre todas as palavras únicas no arquivo de texto. Isso é dividir o arquivo de texto por espaços em palavras e adicionar cada palavra de uma lista a menos que já encontrado nessa lista.

2. Tome todas as palavras que você encontrou e classificá-los em ordem alfabética; a maneira mais rápida de fazer isso é usando Three Way Radix QuickSort . Este algoritmo é difícil de bater no desempenho quando classificando strings.

3. Escreva a lista ordenada para o disco, uma palavra de uma linha.

4. Quando você agora deseja pesquisar o arquivo do documento, ignorá-lo completamente, em vez carregar o arquivo de índice de memória e usar a pesquisa binária para descobrir se uma palavra está no arquivo de índice ou não. busca binária é difícil de bater na busca grande, listas ordenadas.

Como alternativa, você pode mesclar passo (1) e passo (2) dentro de uma única etapa. Se você usar insertion sort (que usa pesquisa binária para encontrar a posição de inserção direito de inserir um novo elemento em uma lista já classificadas), você não só tem um algoritmo rápido para descobrir se a palavra já está na lista ou não, no caso não é, você começa imediatamente a posição correta para inseri-lo e se você sempre inserir novos como isso, você terá automaticamente uma lista ordenada quando você chegar ao passo (3).

O problema é que você precisa para atualizar o índice sempre que as alterações do documento ... no entanto, não seria este ser verdade para a solução de banco de dados também? Por outro lado, a solução de banco de dados, você compra algumas vantagens: Você pode usá-lo, mesmo que os documentos contêm tantas palavras, que os arquivos de índice não iria caber na memória mais (improvável, como até mesmo uma lista de todas as palavras em inglês será caber na memória de qualquer PC do usuário médio); No entanto, se você precisa carregar arquivos de índice de um grande número de documentos, a memória pode se tornar um problema. Ok, você pode resolver isso usando truques inteligentes (por exemplo, pesquisar diretamente dentro dos arquivos que você mapeados para memória usando mmap e assim por diante), mas estes são os mesmos truques bases de dados já usados ??para executar look-ups rápidos, assim, por que re-inventar a roda? Além disso, você também pode evitar problemas entre pesquisar palavras e atualização de índices quando um documento foi alterado bloqueio (isto é, se o banco de dados pode executar o bloqueio para você ou pode executar a atualização ou atualizações como uma operação atômica). Para uma solução web com AJAX exige atualizações da lista, usando um banco de dados é provavelmente a melhor solução (minha primeira solução é bastante adequado, se esta é uma aplicação rodando localmente escrito em uma linguagem de baixo nível, como C).

Se você sentir vontade de fazer tudo isso em uma única chamada select (que pode não ser o ideal, mas quando você dynamacilly conteúdo web atualização com AJAX, que normalmente mostra como a solução causando menos dores de cabeça), você precisa participar de todas as três tabelas juntos. Maio SQL é um pouco enferrujado, mas eu vou dar-lhe uma tentativa:

SELECT COUNT(Document.idDoc) AS NumOfHits, Documents.Name AS Name, Documents.Location AS Location 
FROM Documents INNER JOIN Word_Docs ON Word_Docs.idDoc=Documents.idDoc 
INNER JOIN Words ON Words.idWord=Words_Docs.idWord
WHERE Words.Word IN ('Word1', 'Word2', 'Word3', ..., 'WordX')
GROUP BY Document.idDoc HAVING NumOfHits=X

Ok, talvez isso não é o mais rápido, selecione ... Eu acho que isso pode ser feito mais rápido. De qualquer forma, ele vai encontrar todos os documentos correspondentes que contenham pelo menos uma palavra, depois grupos todos os documentos iguais entre si por ID, contar quantas foram agrupadas togetehr e, finalmente, apenas mostra os resultados onde NumOfHits (o número de palavras encontradas da declaração IN) é igual ao número de palavras dentro da declaração (se você procurar 10 palavras, X é 10).

Answer 3

Não tenho certeza sobre a sintaxe (esta é a sintaxe SQL Server), mas:

-- N is the number of elements in the list

SELECT idDoc, COUNT(1)
FROM Word_Docs wd INNER JOIN Words w on w.idWord = wd.idWord
WHERE w.Word IN ('word1', ..., 'wordN')
GROUP BY wd.idDoc
HAVING COUNT(1) = N

Isto é, sem usar como. Com como as coisas são muito mais complexas.

Answer 4

Google Desktop Search ou uma ferramenta semelhante pode atender às suas necessidades.