construir um número único para uma string em java

Question

Temos a necessidade de ler/gravar mais de 10 milhões de strings em um arquivo.Além disso, não queremos duplicatas no arquivo.Como as strings seriam descarregadas em um arquivo assim que fossem lidas, não as manteríamos na memória.

Não podemos usar o código hash devido a colisões no código hash, devido às quais podemos perder uma string como duplicada.Duas outras abordagens que encontrei em minha pesquisa no Google:

1.Use um algoritmo de resumo de mensagem como MD5 - mas pode ser muito caro para calcular e armazenar.

2.Use um algoritmo de soma de verificação.[não tenho certeza se isso produz uma chave exclusiva para uma string - alguém pode confirmar]

Existe alguma outra abordagem disponível.Obrigado.

Answer 1

Se você está bem com um risco microscópica de colisões, pode usar alguma função de hash, como o MD5, como sugerir e confiar nos hashes.

Outra alternativa, possivelmente com uma pegada de memória maior, é armazenar as cordas, já encontradas, em um Trie (um tipo especial de árvore).

---

Atualização: ainda outra alternativa, seria usar um Filtro de flor. No entanto, isso ainda depende do hash, mas pode ser ajustado para ter uma pequena probabilidade arbitrariamente de colisões.

Answer 2

Armazenar 10 milhões de cordas na memória é realmente muito, então eu entendo o motivo de escrevê -lo para arquivar imediatamente em vez de armazenar em por exemplo TreeSet<String> Primeiro, mas Onde Você gostaria de armazenar as 10 milhões de chaves numéricas únicas com as quais você deseja comparar? Quando você quiser mantê -lo único e numérico (que possui muita base/radix do Littler do que as letras), você não pode tornar a chave mais curta que a própria string já é, para que não salve nenhuma memória. Ou talvez no mais alto com a compressão de dados como o GZIP, mas isso só adicionaria muita sobrecarga. MD5 também é inapropriado desde duas cordas diferentes posso produzir o mesmo hash.

Eu realmente não vejo solução melhor para isso do que usar um RDBMS decente (banco de dados SQL), onde você define a coluna como UNIQUE e lidar com a violação da restrição de acordo. Um RDBMS é altamente otimizado para esse tipo de tarefas.

Se você realmente não pode considerar um banco de dados, precisa reler o arquivo para qualquer entrada existente antes da gravação/Flush. Talvez não muito rápido, mas certamente eficiente em memória.

Answer 3

Não há como fazer uma função que produza uma chave única para uma string, que é mais curta que essa string.
Existem estruturas de dados que podem resolver sua tarefa. B-Tree pode caber se os dados forem grandes o suficiente. Dependendo da natureza de sua contribuição, pode haver maneiras mais eficazes.

Answer 4

A remoção confiável de duplicatas é tão difícil quanto classificar o arquivo.Como outra resposta indica, não há maneira garantida de detectar duplicatas com precisão sem manter uma cópia completa de cada string na memória, o que parece ser exatamente o que você está tentando evitar.

Você poderia manter um índice de hashcodes na memória ou no disco e usá-los para recuperar strings reais do armazenamento de arquivos para comparação, mas isso essencialmente duplicaria o que um banco de dados seria capaz de fazer por você.

Uma alternativa é pós-processar o arquivo quando estiver concluído.O comando sort do UNIX é muito bom para arquivos grandes (Como o comando sort do UNIX poderia classificar um arquivo muito grande?), então espero que a abordagem de linha de comando padrão do UNIX funcione razoavelmente:

    sort my-file-of-strings.txt | uniq > my-filtered-file-of-strings.txt

(Observe que os arquivos devem ser classificados primeiro antes de passar para o uniq para remover duplicatas).

Se você não tiver essas ferramentas (ou equivalentes) disponíveis, poderá sempre tentar implementar você mesmo alguma variante de uma classificação de mesclagem externa.

Answer 5

Se as cordas forem de um pool fixo de seqüências possíveis (n), você pode usar hash perfeito mínimo Para criar uma matriz 0 ... N-1. Um zero no slot determinado pela função de hash perfeita significa que a string não foi vista até agora.

Caso contrário, os únicos meios efetivamente corretos fora de muito da memória e as soluções sugeridas até agora é reler o arquivo antes de decidir gravar a string nela.

Você pode fazer isso da maneira mais eficiente possível pelas partes do mapeamento de memória do arquivo.

Answer 6

Eu realmente acho que a melhor solução é - como alguém já sugeriu - usar um banco de dados.

Se, por algum motivo, você não puder usar um banco de dados, ainda poderá usar um código de hash. Claro que haverá colisões. Basta adicionar algum código para que, ao detectar um código de hash duplicado, seu programa verifique o arquivo para determinar se é uma duplicata genuína ou uma colisão.