검 리트윗을 사용하여 계산 저렴 Python 해싱 알고리즘

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

  •  03-07-2019
  •  | 
  •  

문제

하기 위해서는 감지할 수 있 RT 의 특정 트윗,나는 저장하려는 해시의 각 포맷 트윗 데이터베이스에서.

무엇을 해싱 알고리즘을 사용해야 합니까.암호는 물론 필수적이지는 않습니다.다만 최소한 방법으로 저장하는 데이터가할 수 있는 비교하면 그것은 동일하는 효율적인 방법입니다.

내 첫 번째 시도에서 이었으로 사용하는 md5.그러나 나는 생각이 있을 수 있 해싱하는 알고리즘 훨씬 더 효율적으로 보안이 필요하지 않습니다.

도움이 되었습니까?

해결책

당신은 문자열을 해시하려고합니까? 내장형 유형은 즉시 해시 될 수 있습니다. hash("some string") 그리고 당신은 약간의 int를 얻습니다. Python이 Dictonarys에 사용하는 것과 동일한 기능이므로 아마도 최선의 선택 일 것입니다.

다른 팁

정말로 해시해야합니까? 트위터 메시지는 짧은 (그리고 디스크 공간이 저렴한 디스크 공간) 해시에 시계 사이클을 먹지 않고 전체 메시지를 저장하는 것이 더 낫습니다.

나는 Python에 익숙하지 않지만 (죄송합니다, Ruby Guy가 여기에 타이핑합니다) 몇 가지 시도를 시도 할 수 있습니다.

가정 : 시간이 지남에 따라 수십만 개의 트윗을 저장할 것입니다. 따라서 테이블의 "모든 레코드"에 대해 하나의 해시를 비교하는 것은 비효율적입니다. 또한 RT가 항상 원래 트윗의 카본 사본은 아닙니다. 결국, 원래 저자의 이름은 일반적으로 포함되어 있으며 140 문자 한계 중 일부를 차지합니다. 아마도 "멍청한"해시보다 정확하게 일치하는 솔루션을 사용할 수 있습니까?

  1. 태깅 및 인덱싱

    메시지의 구성 요소 부분을 표준 방식으로 태그하고 색인하십시오. 여기에는 해시 #...., at-marked @.... 및 URL 문자열을 "태그"로 처리하는 것이 포함될 수 있습니다. 소음 단어와 문장 부호를 제거한 후 나머지 단어를 태그로 취급 할 수도 있습니다.

  2. 빠른 검색

    데이터베이스는 여러 그룹 멤버십을 매우 빨리 찾는 데 끔찍합니다 (MySQL 또는 PostgreSQL을 사용한다고 가정하겠습니다. 대신 무료 텍스트 엔진 중 하나를 사용해보십시오스핑크스 검색. 여러 그룹 멤버십을 해결하는 데 매우 빠릅니다 (즉, 키워드가 있는지 확인).

    스핑크스 또는 이와 유사한 것을 사용하여 추출한 모든 "태그"를 검색합니다. 이것은 아마도 "잠재적 원본 트윗"의 작은 결과 세트를 반환 할 것입니다. 그런 다음 유사성 일치 알고리즘을 사용하여 하나씩 비교하십시오 (여기에는 파이썬이 있습니다. http://code.google.com/p/pylevenshtein/)

이제 당신을 세상에 따뜻하게 환영합니다 텍스트 마이닝.

행운을 빕니다!

나는 에코 크리스'의견에 대한 사용하지 않는 해시 모두에서(데이터베이스 엔진할 수 있는 희망을 색인 140 자 필드를 효율적으로).

았다면 이용하고 싶을 해시,MD5 내 첫 번째 선택이 될 것입니다(16 바이트)의 수,SHA-1(20 바이트).

당신이 무엇을 사용하지 않는 합의 문자입니다.할 수 없게 되어 바로 기능하는 것이 더 충돌을(모든 아나그램은 해시 동),플러스 그 느린!

$ 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

여기에는 몇 가지 문제가 있습니다. 첫째, RT가 항상 동일하지는 않습니다. 어떤 사람들은 의견을 추가합니다. 다른 사람들은 추적을 위해 URL을 변경합니다. 다른 사람들은 자신이 rt'ing (창시자가 될 수도 있고 아닐 수도 있음)을 추가합니다.

따라서 트윗을 해시하려면 트윗의 고기로 끓여야합니다. 행운을 빕니다.

위에서 누군가 32 비트로 약 65k 트윗에서 충돌을 시작할 것이라고 언급했습니다. 물론 트윗 #2에서 충돌 할 수 있습니다. 그러나 나는 그 의견의 저자가 2^16 = ~ 65K 이후로 혼란 스러웠지만 2^32 = ~ 4 조. 그래서 당신은 거기에 조금 더 방이 있습니다.

더 나은 알고리즘은 트윗의 "고유 한"부분을 도출하고 지문을 시도하는 것일 수 있습니다. 그것은 해시가 아니며, 독창성을 정의하는 몇 가지 핵심 단어의 지문입니다.

글쎄, 트윗은 140 자에 불과하므로 전체 트윗을 데이터베이스에 저장할 수도 있습니다 ...

그러나 어떻게 든 "해시"를 원한다면 간단한 방법은 트윗에서 모든 캐릭터의 ASCII 값의 합을 가져 오는 것입니다.

sum(ord(c) for c in tweet)

물론, 해시가 일치 할 때마다 동일한 "Sum-Hash"를 제공하는 두 개의 트윗을 찾을 확률은 아마도 무시할 수 없기 때문에 트윗을 동일하게 확인해야합니다.

파이썬의 선반 모듈? http://docs.python.org/library/shelve.html

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top