Detectando Retweets usando computacionalmente barato algoritmos de hashing Python

StackOverflow https://stackoverflow.com/questions/815313

  •  03-07-2019
  •  | 
  •  

Pergunta

De modo a ser capaz de detectar RT de um Piu particular, pretende armazenar hash de cada Piu formatado na base de dados.

O algoritmo de hash devo usar. Cryptic é, naturalmente, não é essencial. Apenas uma maneira mínima de armazenar um conjunto de dados como algo que pode então ser comparado, se é o mesmo, de forma eficiente.

A minha primeira tentativa neste sentido foi usando hashes MD5. Mas eu percebi que não pode ser hash algoritmos que são muito mais eficientes, como a segurança não é necessária.

Foi útil?

Solução

Você está tentando botar um direito corda? Builtin tipos podem ser hash de imediato, basta fazer hash("some string") e você obter algum int. Seus as mesmas utilizações função Python para dictonarys, por isso é provavelmente a melhor escolha.

Outras dicas

Você realmente precisa de hash em tudo? Twitter mensagens são curtas o suficiente (e espaço em disco barato o suficiente) que pode ser melhor apenas para armazenar a mensagem inteira, em vez de comer-se ciclos de clock para hash.

Eu não estou familiarizado com o Python (desculpe, Ruby cara digitação aqui), contudo, você poderia tentar algumas coisas.

Pressupostos: Você provavelmente vai ser armazenar centenas de milhares de tweets ao longo do tempo, por isso comparando um hash de contra "todos os registros" na tabela será ineficiente. Além disso, RTs nem sempre são cópias de carbono do Piu originais. Afinal, o nome do autor original é normalmente incluídos e leva um pouco do limite de 140 caracteres. Então, talvez você poderia usar uma solução que jogos mais precisão do que um hash "burro"?

  1. Tagging & indexação

    Tag e índice das partes componentes de a mensagem de uma forma padrão. este poderia incluir o tratamento de hash # ...., at-marcada @ .... e cadeias de URL como "Tag". Depois de remover palavras de ruído e pontuação, você também pode tratar as palavras restantes como marcas também.

  2. pesquisa rápida

    Os bancos de dados são terríveis na constatação associação de grupo múltiplo muito rapidamente (eu vou assumir o seu usando MySQL ou PostgreSQL, que são terrível neste). Em vez de tentar um dos motores de texto livre, como Esfinge Pesquisa . Eles estão muito muito rápida de resolver adesão grupo múltiplo (i.e. verificar se as palavras-chave estão presentes).

    Usando Esfinge ou similar, buscamos em todas as "tags" que extraído. este provavelmente irá retornar um pequeno resultar conjunto de "potenciais tweets originais". Em seguida, compará-los um por um usando o algoritmo de correspondência de similaridade (Aqui é uma em Python http://code.google.com/p/pylevenshtein/)

Agora, deixe-me damos boas-vindas ao mundo do mineração de texto .

Boa sorte!

repito comentário Chris' sobre não usar um hash em tudo (o seu motor de banco de dados pode espero campos índice de 140 caracteres de forma eficiente).

Se você queria usar um hash, MD5 seria a minha primeira escolha, bem como (16 bytes), seguido por SHA-1 (20 bytes).

Faça o que fizer, não use soma de caracteres. Eu não pode vir imediatamente com uma função que teria mais colisões (todos os anagramas de hash o mesmo), mais ele é mais lento! 

$ python -m timeit -s 'from hashlib import md5' 'd=md5("There once was a man named Michael Finnegan.").digest()'
100000 loops, best of 3: 2.47 usec per loop
$ python -m timeit 'd=sum(ord(c) for c in "There once was a man named Michael Finnegan.")'
100000 loops, best of 3: 13.9 usec per loop

Existem alguns problemas aqui. Em primeiro lugar, da RT nem sempre são idênticos. Algumas pessoas adicionar um comentário. Outros mudar a URL para o rastreamento. Outros acrescentam na pessoa que eles são RT'ing (que pode ou não ser o autor).

Então, se você está indo de hash o tweet, é necessário reduzi-lo à carne do tweet, e só hash que. Boa sorte.

Acima, alguém mencionou que, com 32-bits, você vai começar a ter colisões em cerca de 65 mil tweets. Claro, você poderia ter colisões em Tweet # 2. Mas eu acho que o autor desse comentário foi confuso, já que 2 ^ 16 = ~ 65K, mas 2 ^ 32 = ~ 4 trilhões. Então você tem um pouco mais de espaço lá.

Um algoritmo poderia ser melhor para tentar derivar as peças "únicas" do tweet, e impressões digitais dele. Não é um hash, é uma impressão digital de algumas palavras-chave que definem a exclusividade.

Bem, tweets são apenas 140 caracteres, então você pode até mesmo armazenar todo o tweet no banco de dados ...

mas se você realmente quer "haxixe"-los de alguma forma, uma maneira simples seria tomar apenas a soma dos valores ASCII de todos os personagens no tweet: 

sum(ord(c) for c in tweet)

Claro que, sempre que você tem um jogo de hashes, você deve verificar os tweets-se para mesmice, porque a probabilidade de encontrar dois tweets que dão o mesmo "soma-de hash" é provavelmente não negligenciável.

módulo de prateleira do Python? http://docs.python.org/library/shelve.html

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top