비슷한 항목을 찾기 위해 Bloom Filters와 Minhashing을 구현해야하는 애플리케이션이 있습니다. K- 길이의 문자열에 Minhashing
내가 블룸 필터가 구현해야하지만 난 그것을 수행 할 Minhashing 부분을 이해하고 있는지 확인해야합니다 : 모든,문서의 모든 문자열을 섞어야합니까? 문제는 내가 정말로이 문서에서 나를 돕기위한 것을 찾을 수 없다는 것입니다. 두 개의 문서에 관한 것이고 하나의 문자열에 대한 문자열은 결코 아닙니다.
그래서 사용자가 문자열을 입력하면 응용 프로그램은 단일 문서 내에서 가장 유사한 문자열을 찾습니다. "유사성"이란 Levenstein 거리 ("고양이"는 "쥐"및 "카트"와 비슷한 것으로 간주됩니다) 또는 다른 측정 값과 같은 것을 의미합니까? 유사한 문단, 유사한 문장, 유사한 문구 또는 유사한 단어를 찾는 당신 (대략 말하기)입니까? 이것들은 중요한 고려 사항입니다.
또한 한 문자열과 한 세트의 문자열을 비교한다고 가정 해보십시오. 이 문자열은 무엇입니까? 문장? 단락? 여러 단락 (또는 여러 문장 또는 what-have-you)에 걸쳐 유사점을 찾고 싶지 않다면 문서를 여러 개의 개별 문자열로 생각하는 것이 좋습니다. 그렇지 않으면 하나의 긴 문자열로 생각해야합니다.
MinHash 알고리즘은 모든 문서를 동시에 메모리에 저장할 수없고 모든 문서를 개별적으로 비교하는 것이 n 제곱 문제 일 때 많은 문서를 서로 비교하는 알고리즘입니다. MinHash는 일부 대상에만 해시를 저장함으로써 이러한 문제를 극복하고 그 결과 일부 정확도를 희생합니다. MinHash는 필요하지 않습니다. 대상에 네 글자 - 그램을 사용하여 메모리에 모든 싱글을 간단하게 저장할 수 있습니다. 그러나 단어 순서를 바꾸지 않으려면 Smith-Waterman algorithm이 더 적합 할 수 있습니다 (here 참조).
사용자가 긴 단어 열을 입력 할 것으로 예상되는 경우 대상에 단어를 적용한 결과가 좋을 수 있습니다. 예를 들어, 3 단어 그램은 공백 문자, 대소 문자 및 구두점의 차이를 무시합니다.
4 문자 그램을 생성하는 것은 간단합니다. "고양이는 매트에 앉았습니다"는 "The", "hec", "e ca", "cat"등을 생성합니다. 사용자가 검색 문자열을 입력하면 동일한 방식으로 물결이 생기고 가장 많은 수의 공유 대상물이 포함 된 단락을 검색 할 수 있습니다. 비교의 효율성을 위해 대상 포진을 문자열로 저장하는 대신 FNV1a 또는 비슷한 저렴한 해시를 사용하여 해시로 저장할 수 있습니다.
대상 포진은 문자가 아닌 단어 (예 : "고양이 앉아", "고양이 앉아", "앉았다")로 만들 수도 있습니다. 이것은 더 큰 텍스트 조각 (예 : 30 단어 이상)에서 더 잘 나타나는 경향이 있습니다. 나는이 접근법을 취하는 경우 일반적으로 공백, 대소 문자 및 구두점의 모든 차이를 무시합니다.
문단 전체를 대상으로하는 일치 항목을 찾고 싶다면, 모든 슁글에 대한 문자 위치를 저장하고 가능한 일치 항목의 다양한 구성을 고려해야하며, 널리 대상 포진은 흩어져 있습니다.따라서 코드가 복잡해질 수 있습니다. 스미스 - 워터맨과 같은 Levenstein 기반 솔루션을 사용하는 것은 단어 순서가 바뀌지 않더라도 심각하게 고려해야합니다.
필자가 어떻게 사용하고 있는지 잘 모르겠지만 블룸 필터가 도움이 될 것으로 생각하지 않습니다. 블룸 필터 은 일 수 있습니다. 문서의 구조가 매우 복잡한 경우 유용 할 수 있습니다. 가능한 문자열 집합과 그 중 하나의 존재를 검색하고 있습니다. 하지만 자연어의 경우에는 매우 유용 할 것입니다.