자동 완성을위한 알고리즘?

자동 완성을위한 알고리즘?

---

사용자가 Google에서 검색어를 입력 할 때 추천 검색어를 제공하는 데 사용되는 알고리즘을 말합니다.

나는 주로 다음 사항에 관심이 있습니다. 1. 가장 중요한 결과 (일치하는 항목보다 쿼리 가능성이 가장 높음) 2. 하위 문자열 일치 3. 퍼지 일치

Trie 또는 일반화 된 trie를 사용하여 일치 항목을 찾을 수 있다는 것을 알고 있지만 위의 요구 사항을 충족하지 못할 것입니다.

앞서 여기에서 질문 한 유사한 질문

---

(heh) 멋진 퍼지 / 부분 문자열 일치 알고리즘에 대해서는 Damn Cool Algorithms를 확인하십시오.

• http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
• http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

이것은 시도를 대체하는 것이 아니라 시도에서 무차별 대입 조회를 방지합니다. 이는 여전히 큰 승리입니다. 다음으로 트라이의 크기를 제한하는 방법을 원할 것입니다.

• 전 세계적으로 사용 된 최근 / 상위 N 단어를 유지합니다.
• 각 사용자에 대해 해당 사용자의 최근 / 상위 N 단어를 유지합니다.

마지막으로, 가능할 때마다 조회를 방지하고 싶습니다.

• 캐시 조회 결과 : 사용자가 검색 결과를 클릭하면이를 매우 빠르게 제공 한 다음 전체 부분 / 퍼지 조회를 비동기 적으로 가져올 수 있습니다.
• 조회 결과 미리 계산 : 사용자가 "appl"을 입력 한 경우 "apple", "apply"를 계속할 가능성이 높습니다.
• 데이터 프리 페치 : 예를 들어 웹 앱은 JS에서 무차별 대입 검색을 실행할 수있을만큼 작은 결과 집합을 브라우저에 보낼 수 있습니다.

---

이 문제에 대한 좋은 해결책은 삼항 검색 트리 이상을 통합하는 것입니다. Ngrams 및 Shingles (Phrases)가 필요합니다. 단어 경계 오류도 감지해야합니다. "hell o"는 "hello"여야합니다. ... "whitesocks"는 "white socks"여야합니다. 이는 전처리 단계입니다. 데이터를 제대로 전처리하지 않으면 귀중한 검색 결과를 얻을 수 없습니다. 삼항 검색 트리는 단어가 무엇인지 파악하고 입력 된 단어가 색인에서 유효한 단어가 아닐 때 관련 단어 추측을 구현하는 데 유용한 구성 요소입니다.

Google 알고리즘은 구문 제안 및 수정을 수행합니다. Google 알고리즘에는 컨텍스트 개념도 있습니다. 검색하는 첫 번째 단어가 날씨와 관련이 있고 "weatherforcst"대 "monsoonfrcst"대 "deskfrcst"를 결합하는 경우-내 추측은이면에서 순위가 ​​변경되고 있습니다. 발견 된 첫 번째 단어를 기반으로 한 제안-예측 및 날씨는 관련 단어이므로 예측은 뜻 했음에서 높은 순위를 차지합니다.

단어 부분 (ngram), 구문 용어 (대상 포진), 단어 근접성 (단어 클러스터링 인덱스), 삼항 검색 트리 (단어 조회).

---

구글의 정확한 알고리즘은 알려지지 않았지만 사용자 입력에 대한 통계 분석을 통해 작동 한다고 합니다. 대부분의 경우에 적합하지 않은 접근 방식입니다. 보다 일반적으로 자동 완성은 다음 중 하나를 사용하여 구현됩니다.

• 나무 . 트리 구조 (접두사 트리, 접미사 트리, dawg 등)에서 검색 가능한 텍스트를 인덱싱하면 메모리 저장을 희생하면서 매우 빠른 검색을 실행할 수 있습니다. 트리 순회는 대략적인 일치를 위해 조정될 수 있습니다.
• 패턴 파티셔닝 . 텍스트를 토큰 (ngram)으로 분할하면 간단한 해싱 체계를 사용하여 패턴 발생에 대한 검색을 실행할 수 있습니다.
• 필터링 . 잠재적 일치 항목을 찾은 다음 순차적 알고리즘을 적용하여 각 후보를 확인합니다.

에서 봐 완전히 자바 자동 완성 라이브러리가 구현 후자의 몇 가지 개념.

---

특정 범위 내에있는 퍼지 일치를 찾는 데 사용할 수있는 soundex 및 levenshtein distance 와 같은 도구 가 있습니다.

Soundex는 유사하게 들리는 단어를 찾고 levenshtein distance는 다른 단어에서 특정 편집 거리 내에있는 단어를 찾습니다.

---

Firefox의 Awesome bar 알고리즘 살펴보기

Google 제안은 수백만 개의 인기 검색어와 과거 관련 검색어를 고려하기 때문에 유용합니다.

그래도 좋은 완료 알고리즘 / UI가 없습니다.

1. 부분 문자열을하지 않습니다
2. 비교적 단순한 단어 경계 접두사 알고리즘처럼 보입니다.
   예 : 시도 tomcat tut-> "tomcat tutorial"을 올바르게 제안 하십시오 . 이제 시도 tomcat rial-> 제안 없음)-:
3. "이것을 의미 했습니까?"를 지원하지 않습니다. -Google 검색 결과에서와 같이.

---

부분 문자열 및 퍼지 일치의 경우 Levenshtein 거리 알고리즘이 상당히 잘 작동했습니다. 나는 그것이 자동 완성 / 제안의 업계 구현만큼 완벽하지 않은 것임을 인정할 것이다. Google과 Microsoft의 Intellisense 모두 ​​더 나은 작업을 수행합니다.이 기본 알고리즘을 개선하여 서로 다른 문자열을 일치시키는 데 필요한 편집 작업의 종류를 평가했기 때문이라고 생각합니다. 예를 들어 두 문자를 조바꿈하면 2 개가 아닌 1 개 연산으로 만 계산됩니다 (삽입 및 삭제).

하지만 그래도 충분히 가깝다는 것을 알았습니다. 다음은 C #으로 구현 한 것입니다.

// This is the traditional Levenshtein Distance algorithem, though I've tweaked it to make
// it more like Google's autocomplete/suggest.  It returns the number of operations 
// (insert/delete/substitute) required to change one string into another, with the 
// expectation that userTyped is only a partial version of fullEntry.
// Gives us a measurement of how similar the two strings are.
public static int EditDistance(string userTyped, string fullEntry)
{
    if (userTyped.Length == 0) // all entries are assumed to be fully legit possibilities 
        return 0; // at this point, because the user hasn't typed anything.

    var inx = fullEntry.IndexOf(userTyped[0]);
    if (inx < 0) // If the 1st character doesn't exist anywhere in the entry, it's not
        return Int32.MaxValue; // a possible match.

    var lastInx = inx;
    var lastMatchCount = 0;
TryAgain:
    // Is there a better starting point?
    var len = fullEntry.Length - inx;
    var matchCount = 1;
    var k = 1;
    for (; k < len; k++)
    {
        if (k == userTyped.Length || userTyped[k] != fullEntry[k + inx])
        {
            if (matchCount > lastMatchCount)
            {
                lastMatchCount = matchCount;
                lastInx = inx;
            }
            inx = fullEntry.IndexOf(userTyped[0], inx + 1);
            matchCount = 0;
            if (inx > 0)
                goto TryAgain;
            else
                break;
        }
        else
            matchCount++;
    }
    if (k == len && matchCount > lastMatchCount)
        lastInx = inx;

    if (lastInx > 0)
        fullEntry = fullEntry.Substring(lastInx); // Jump to 1st character match, ignoring previous values 

    // The start of the Levenshtein Distance algorithem.
    var m = userTyped.Length;
    var n = Math.Min(m, fullEntry.Length);

    int[,] d = new int[m + 1, n + 1]; // "distance" - meaning number of operations.

    for (var i = 0; i <= m; i++)
        d[i, 0] = i; // the distance of any first string to an empty second string
    for (var j = 0; j <= n; j++)
        d[0, j] = j; // the distance of any second string to an empty first string

    for (var j = 1; j <= n; j++)
        for (var i = 1; i <= m; i++)
            if (userTyped[i - 1] == fullEntry[j - 1])
                d[i, j] = d[i - 1, j - 1];       // no operation required
            else
                d[i, j] = Math.Min
                           (
                             d[i - 1, j] + 1,  // a deletion
                             Math.Min(
                             d[i, j - 1] + 1,  // an insertion
                             d[i - 1, j - 1] + 1 // a substitution
                             )
                           );

    return d[m, n];
}

---

문제에 대한 전체적인 디자인을 찾고 있다면 https://www.interviewbit.com/problems/search-typeahead/ 에서 콘텐츠를 읽어보십시오 .

트라이를 사용하는 순진한 접근 방식을 통해 자동 완성을 구축 한 다음이를 기반으로 구축합니다. 또한 특정 사용 사례에 맞게 샘플링 및 오프라인 업데이트와 같은 최적화 기술을 설명합니다.

솔루션의 확장 성을 유지하려면 트라이 데이터를 지능적으로 분할해야합니다.

---

완전히 다른 데이터 구조를 추구하는 것보다 전문적인 시도를 구성하는 것이 더 나을 것이라고 생각합니다.

각 잎에 해당 단어의 검색 빈도를 반영하는 필드가있는 트라이에서 기능이 나타나는 것을 볼 수있었습니다.

The search query method would display the descendant leaf nodes with the largest values calculated from multiplying the distance to each descendant leaf node by the search frequency associated with each descendant leaf node.

The data structure (and consequently the algorithm) Google uses are probably vastly more complicated, potentially taking into a large number of other factors, such as search frequencies from your own specific account (and time of day... and weather... season... and lunar phase... and... ). However, I believe that the basic trie data structure can be expanded to any kind of specialized search preference by including additional fields to each of the nodes and using those fields in the search query method.

참고URL : https://stackoverflow.com/questions/2901831/algorithm-for-autocomplete