특정 트윗의 RT를 감지 할 수 있도록 데이터베이스에 각 형식화 된 트윗의 해시를 저장할 계획입니다.계산 방법으로 저렴한 Python 해싱 알고리즘을 사용하여 리트 윗 감지
어떤 해시 알고리즘을 사용해야합니까? 물론 암호는 필수적인 것은 아닙니다. 데이터를 효율적인 방법으로 동일하게 비교할 수있는 최소한의 방법으로 데이터를 저장하는 것입니다.
첫 번째 시도는 md5 해시를 사용하는 것이 었습니다. 하지만 보안이 필요하지 않으므로 훨씬 더 효율적 인 해싱 알고리즘이있을 수 있다고 생각했습니다.
문자열을 해시하려고하는 중입니까? Builtin 타입은 즉시 해시 될 수 있으며, 단지 hash("some string")을 수행하면 int가됩니다. 파이썬이 dictonarys를 위해 사용하는 것과 같은 함수이기 때문에 아마 최선의 선택 일 것입니다.
하지만 32 비트 값을 생성하지는 않습니까? 이 애플리케이션은 메시지를 삭제하고 해시에만 의존하기 때문에 충돌 방지 기능이 더 필요하다고 생각합니다. 32 비트 값을 사용하면 스티븐 프라이 (Stephen Fry)의 30 시간과 같은 65k 트윗 내에서 충돌이 발생할 것으로 예상됩니다. –
파이썬의 쉘브 모듈? http://docs.python.org/library/shelve.html
정말 해시가 필요합니까? 트위터 메시지는 충분히 짧아서 (디스크 공간은 충분히 쌉니다), 해시하기 위해 시계 사이클을 먹는 것이 아니라 전체 메시지를 저장하는 것이 좋습니다.
음, 주어진 140 자 문자열과 수천 개의 그러한 문자열을 비교하는 것은 계산 상으로 많은 비용이들 것입니다. 나는 count (해시)를 사용하여 db를 쿼리하는 것이 더 간단하고 효율적이라고 생각했습니다. 당신이 틀린 경우에 나에게 굴복하십시오. –
항상 당신의 트윗을 정렬하고 이진 검색을 사용하면 가능할 수 있습니다. 데이터베이스가 정말 큰 경우 기수 검색을 사용하십시오. (선형 실행 시간, 얼마나 멋지 죠?) –
리트 윗은 종종 동일하지 않습니다.당신이 일종의 "normalizer"를 먼저 실행하지 않는 한 해시는 이것을 알 수 없습니다. – pchap10k
음, 트윗 당신도 데이터베이스의 전체 트윗을 저장할 수 있도록에만 140 자 ..., 긴
하지만 당신이 정말로 단지를에 "해시"그들이 어떻게 든, 간단한 방법이 될하려는 경우 트윗에있는 모든 문자의 ASCII 값의 합을 : 물론
sum(ord(c) for c in tweet)
당신이 해시의 일치있을 때마다, 당신은 동일성에 대한 트윗 스스로 확인해야 두 개의 트윗을 찾을 가능성 때문에 그 같은 "sum-hash"를주는 것은 무시할 수 없을 정도입니다.
정답을 제공하는 단순 해시가 있습니까 _almost always_ –
나는 해시를 전혀 사용하지 않는다는 Chris의 의견을 남깁니다 (데이터베이스 엔진은 140 자 필드를 효율적으로 색인 할 수 있습니다).
해시를 사용하려는 경우 MD5가 가장 먼저 선택되고 (16 바이트) SHA-1 (20 바이트)가 뒤 따릅니다.
무엇을 하든지 문자 합계를 사용하지 마십시오. 나는 더 많은 충돌을 가질 수있는 함수 (모든 anagrams 해시가 동일 함)를 즉시 얻을 수 없으며, 더 느리다!
$ 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
"합"은 끔찍한 해시 코드입니다. 하지만 140 * 255는 35700이고 내 시스템에는 16 비트 만 저장하면됩니다. –
맞습니다. 손가락이 뇌보다 조금 더 빨리 움직였습니다. –
저는 파이썬에 익숙하지 않습니다. (미안하지만 여기에 입력하는 루비 남자) 그러나 몇 가지 시도해 볼 수 있습니다.
가정 : 당신은 가능성이 매우 비효율적 일 것이다 표에서 "모든 레코드"에 대해 하나의 해시를 비교, 시간이 지남에 트윗 수십만 저장됩니다. 또한 RT는 항상 원본 트윗의 카피 본문이 아닙니다. 결국 원저자의 이름이 일반적으로 포함되며 140 자 제한 중 일부를 차지합니다. 따라서 "멍청한"해시보다 정확하게 일치하는 솔루션을 사용할 수 있습니까?
태그 및 인덱스 표준 방식으로 메시지의 구성 부품 & 인덱싱 태그. 이 은 해쉬 된 # ...., at @ 및 URL 문자열 "tags"를 처리 할 수 있습니다. 노이즈 단어 과 구두점을 제거한 후에도 나머지 단어를 으로 처리 할 수도 있습니다.
빠른 검색
데이터베이스가 매우 빠르게 여러 그룹 구성원을 찾는 끔찍하다 (나는 당신이에서 끔찍한 입니다 MySQL의 또는 PostgreSQL을,를 사용하여 가정합니다). 대신 Sphinx Search과 같은 무료 텍스트 엔진 중 하나를 시도해보십시오. 여러 그룹 구성원을 해결할 때 매우 빠르게 입니다 (예 : 키워드가 있는지 확인).
스핑크스 또는 유사 물을 사용하여 우리가 추출한 모든 "태그"를 에서 검색합니다. 이 은 아마도 "잠재적 인 원래 트윗"의 결과 집합 인 작은 을 반환합니다. 그리고 따뜻하게 텍스트 마이닝의 세계에 오신 것을 환영 지금 나를 보자 유사성 매칭 알고리즘 (여기 파이썬 http://code.google.com/p/pylevenshtein/의 하나입니다)
를 사용하여 하나 에 의해 그들에게 하나를 비교합니다.
행운을 빈다.
물론 나는 모든 @words와 구두점을 "지저귐을 청소해야"합니다. 태그 지정, 그룹화가 아닌 데이터베이스를 쿼리 (해시)로 쿼리 할 수있는 고유 한 값을 생성하는 것이 더 간단하지 않습니까? –
RT 샘플을 분석하고 거의 동일하다고 확인 했습니까? 당신이 이것을 의지 할 수 있다면 해시가 더 간단해질 것입니다. 그러나 내 신속한 야생화 추측은 RT의 10-20 %가 원본과 다를 게없는 것으로 보입니다. 높은 정확도가 필요하다면, RT처럼 보이는 트윗 (예 : RT @ .... ","via @ .... ","Retweet @ ")의 의미있는 무작위 표본 (1000-10000)을 얻으십시오. .. "또는"@ ... said ") 원본과 얼마나 일치하는지 측정하십시오. 정확도가 그다지 중요하지 않은 경우 시간을 절약하고 해시하면됩니다. 빠른 해시 검색에 대한 아이디어도 있었으므로 아래에 설명하겠습니다. : D – pchap10k
여기에 몇 가지 문제가 있습니다. 첫째, RT가 항상 동일하지는 않습니다. 어떤 사람들은 의견을 추가합니다. 다른 것들은 추적을 위해 URL을 변경합니다. 다른 사람들은 RT'ing (발신자가 될 수도 그렇지 않을 수도 있음)이라고 덧붙입니다.
트윗을 해시하려면 트위터의 고기까지 끓여야하며 해시 만하면됩니다. 행운을 빕니다.
이상, 누군가 32 비트로 언급하면 약 65K 트윗에서 충돌이 시작됩니다. 물론 짹짹 # 2에 충돌이있을 수 있습니다. 그러나 그 의견의 저자는 2^16 = ~ 65K이지만 2^32 = ~ 4 조로 혼동되었다고 생각합니다. 그래서 좀 더 방이 있습니다.
더 나은 알고리즘은 트위터의 "고유 한"부분을 추출하고 지문을 추출하려고하는 것일 수 있습니다. 그것은 해시가 아닙니다. 고유성을 정의하는 몇 가지 핵심 단어의 지문입니다.
그래, 나는 멈추는 말을 떨어 뜨리고 일종의 단어 주파수 지문을 만드는 것이 여기 갈 길이라고 생각한다. –
CRC 저장 및 비교는 어떻습니까? – dirkgently
일부 문제에 대해 생각해보십시오. re-tweet은 're-tweet'에 대한 엄격하고 빠른 규칙이 없으므로 패턴 일치 문제에 더 가깝습니다. 결과적으로 원래 트윗의 일부만 사용할 수 있으므로 해시가 작동하지 않을 수 있습니다. 텍스트 인덱서를 사용하려면 – jottos
@jottos이 목적을 위해 RT로 시작하는 모든 단어는 retweets이며 90을 포함한다고 가정합니다. %의 오른쪽. 실질적으로 충분합니다. 나는 모든 @ 워드 RT 등의 트윗을 "정리"해야 할 것이므로 해싱이 가능할 수있다. –