그래서 여기에는 다양한 주제가 포함되어 있으며 그 중 일부는 StackOverflow에서 다루어 졌음을 알 수 있습니다 (예 : this question). 비슷하게 Partial String Matching과 Approximate String Matching이 인기있는 알고리즘 토론입니다. 그러나이 두 가지 아이디어를 함께 사용하여 문제를 해결할 필요가있는 경우에는 매우 비효율적 인 것처럼 보입니다. 두 가지 문제를 하나의 솔루션에 효율적으로 결합하는 방법을 찾고 있습니다.AppEngine 근사 부분 문자열 매칭 알고리즘
지금은 AppEngine을 Java 및 영구 데이터 저장소와 함께 사용하고 있습니다. 일을 더 쉽게하기 위해 쿼리에서 산술적 인 사용법을 사용하지 않는 것 같아서 일부 사전 계산을하고 데이터베이스의 추가 필드로 저장하는 것을 고려 중입니다. 본질적으로, 이것은 친구와 내가 매칭을위한 시스템을 어떻게 구현할 것인가에 관한 생각이었고, 나는 그것을 더 효율적으로 만드는 방법에 대한 제안을 다소간 기대했었다. 이미 존재하는 것이 더 나은 것으로 유리하게 폐기되어야한다면, 그것을 처리 할 수 있습니다.
검색을 수행하기위한 기본 예제부터 시작해 보겠습니다. 다음과 같은 말도 안되는 문장을 생각해보십시오 :
격리 레이어는 위선적 인 쓰레기 아래에 주춧돌을 래핑합니다. 사용자가 검색을 수행하면
isalatig PRI의
나는이 문자열에 대한 상당히 좋은 시작이 일치 될 것이라고 생각하고, 값이해야 반환되었습니다. 우리가 사용하려고하는 현재의 방법은 기본적으로 테스트 나누기에 가치를 할당합니다. 기본적으로 각 문자
A: 2 B: 3 C: 5
D: 7 E: 11 F: 13
...
는 소수에 매핑되는 다음과 같은 데이터가있는 테이블이 (여러 문자가 변화를하지 않는 단 하나의 문자 필요). 그리고 쿼리 문자열이 데이터베이스의 문자열을 나누는 경우 값은 가능한 일치 항목으로 반환됩니다.
그런 다음 중지 단어로 나열되지 않은 키워드는 검색 문자열의 주어진 임계 값 (현재 Levenshtein 거리 사용)에서 가능한 일치 항목의 단어 하위 문자열을 시작하는지 확인하기 위해 검색 문자열과 비교됩니다.
distance("isalatig", "isolating") == 2
distance("pri", "principal") == 0 // since principal has a starting
// substring of pri it passes
각 쿼리에 대한 총 거리는 오름차순 위를 기록하고 상단 n 값은 다음 질의를하고있는 사람에게 다시 반환됩니다.
이이 같은 시나리오를 다루는 나의 처음이기 때문에 비록 내가 아마 (또는 내 모든 생각이 잘못 될 수 있음) 매우 중요한 뭔가가있어 실현, 알고리즘의 기본 개념이다. 구현하려는 현재 상황을 처리하는 가장 좋은 방법은 무엇입니까? AppEngine이 현재하고있는 일에 대처하기 위해 현재 제공하는 유틸리티가 있다면 마찬가지로 알려주십시오.
SearchableModel은 파이썬 전용으로 보이며 특별히 Java를 사용하려고합니다. Google Site Search는 또한 사용자 유형에 따라 검색을 동적으로 만들려고하기 때문에 문제가되지 않습니다. 또한, 특히 안드로이드 애플리케이션의 일부로 구현되어 있으므로 실제로 작동하지 않을 수도 있습니다. FTS가 AppEngine 용으로 출시 될 때까지 운이 좋지 않은 것처럼 보입니다. – ashays