데이터베이스에 문자열 집합이 있습니다. 각 세트에는 500 명 이하의 회원이 있고, 수만 세트가 있으며, 문자열은 자연 언어입니다. 각각의 세트 내에서 중복 문자열을 감지하고 싶습니다. 새 문자열은 기존 세트와 비교되고 고유 한 경우 데이터베이스에 추가됩니다.중복 텍스트 감지/해시
(매우) 유사한 문자열을 찾는 데 효과적인 해싱 알고리즘이 있습니까? 예를 들어, 문자열의 단어 수는 같지만 인코딩이 약간 다를 수 있습니다 (UTF-8과 Latin-1).
처음에는 일종의 정규화를 수행해야합니다. 아마도 모든 텍스트를 단일 인코딩 (예 : UTF-8)으로 변환해야합니다. 대/소문자 접기 (Unicode normalizations)를 수행하고 각 세트를 정렬하는 방법도 있습니다 (저장 방법에 따라 다름).
정확하게 일치하는 항목을 찾고 싶을 지, 아니면 "비슷한"문자열 세트를 찾으려고하는지 묻는 질문에 대해 (나에게) 불분명합니다. 정규화가 고려되면 정확한 일치에만주의를 기울이면 꽤 많이 완료됩니다. 문자열 세트의 정규화 된 형식에 대한 인덱스 만 있으면 정규화하여 새 세트를 빠르게 찾을 수 있습니다.
거의 일치하는 항목을 찾으려면 유사성 해싱과 같은 일을하고 싶을 것입니다. Locality Sensitive Hashing에 Wikipedia 기사는 다수 기술을 기술한다.
이러한 기법의 기본 아이디어는 각 문자열 h [0]에서 h [n]에 대해 매우 손실이 많은 해시를 계산하는 것입니다. 새 문자열 세트를 찾으려면 해시를 계산하고 각각을 살펴보십시오. 적어도 하나의 일치 항목을 얻는 항목은 모두 '유사'하며, 일치하는 항목이 많을수록 (그리고 사용자가 원하는 항목을 선택할 수 있습니다.)
데이터베이스에 문자열이 500 개 밖에없는 경우 각 문자열과 직접 비교할 수 있습니다. 먼저 표준 표현으로 변환합니다 (예 : UTF-16). Levenshtein distance은 두 문자열의 유사성을 비교할 수있는 좋은 방법입니다.
많은 세트가 있기 때문에, Difflib 등이 제공하는 유사 거리를 사용하면 실행 가능하지 않습니다. – wehriam
간단한 해답은 "유사한"아이디어에 맞는 좋은 해시 매개 변수가 무엇인지 추측하는 것입니다.
아마도 모든 문자 (A)의 합계와 인접한 문자 (B) 간의 차이점의 합계와 같은 것으로 작동 할 수 있습니다. 각각의 새 문자열에 대해 A 및 B 값을 사용하여 훨씬 더 작은 유사한 문자열 세트를 빠르게 찾은 다음 이들을 더 자세히 비교하십시오.
이것은 아마도 가장 순수한 해결책은 아니지만 사실상 많은 문제가이 방법으로 해결됩니다. 이 외에도 유전학에서 비슷한 문제를 해결하는 데는 현재 상당한 노력이 필요하다고 생각합니다. 그러나이 문제에 대한 일반적인 해결책은 없다고 생각합니다.
이것은 잔인 할 수도 있지만, 파이썬을 기반으로하는 NLTK (Natural Language Toolkit)을 시도해 볼 수 있습니다.
유용 할 수있는 기능 중 하나는 analyze sentence structure입니다. 물론 문법 구조는 같지만 단어와 의미가 다르므로 일부 문자열은 중복으로 표시 될 수 있습니다.
확률 및 분류 기능을 사용할 수도 있습니다.
당신은 미친 및 잠재 의미 분석/매핑과 특이 값 분해를 시도 할 수 : latent semantic mapping
함께 SVDLIBC와 함께 가야 아주 쉽게이다.
This post 내 블로그에 관심이있을 수 있습니다.
알고리즘에 대한 설명과 코드 링크가 제공됩니다. 간단히 말해 입력의 내용이나 구조에 대한 가정을하지 않고 모든 입력 문서에 대해 일정한 길이의 서명을 생성하는 n 그램 기반 접근 방식입니다.
shingling이 접근 방법의 일부일 수 있습니다. http://nlp.stanford.edu/IR-book/html/htmledition/near-duplicates-and-shingling-1.html – wehriam
원하는 경우 메타 폰이나 soundex를 저장할 수 있습니다. 비슷한 물건 –
shingling. 시원하고 처음 들었습니다. – si28719e