건초 더미의 바늘: 멋진 대규모 텍스트 검색 알고리즘 자습서

"텍스트 검색"이라는 용어를 접할 때 일반적으로 사용자가 입력할 때 하나 이상의 검색어를 빠르게 찾을 수 있도록 하는 방식으로 인덱싱된 큰 텍스트 본문을 생각합니다. 이것은 많은 솔루션이 존재하는 컴퓨터 과학자에게 고전적인 문제입니다.

그러나 반대 시나리오는 어떻습니까? 사전에 인덱싱에 사용할 수 있는 항목이 검색 구문 그룹이고 런타임에만 검색을 위해 제공되는 많은 텍스트가 있는 경우에는 어떻게 될까요? 이 질문은 이 tri 데이터 구조 자습서에서 해결하고자 하는 것입니다.

애플리케이션

이 시나리오의 실제 적용은 여러 의학 논문을 의학적 상태 목록과 일치시키고 어떤 논문이 어떤 상태에 대해 논의하는지 찾는 것입니다. 또 다른 예는 방대한 판례를 탐색하고 그들이 참조하는 법률을 추출하는 것입니다.

직접 접근

가장 기본적인 접근 방식은 검색 구문을 반복하고 각 구문의 텍스트를 하나씩 검색하는 것입니다. 이 접근 방식은 잘 확장되지 않습니다. 다른 내부에서 문자열을 검색하는 것은 복잡도가 O(n) 입니다. m개의 검색 구에 대해 이를 반복하면 끔찍한 O(m * n) 이 됩니다.

다음 C# 스니펫에서 볼 수 있듯이 구현이 간단하다는 직접적인 접근 방식의 장점은 다음과 같습니다.

 String[] search_phrases = File.ReadAllLines ("terms.txt"); String text_body = File.ReadAllText("body.txt"); int count = 0; foreach (String phrase in search_phrases) if (text_body.IndexOf (phrase) >= 0) ++count;

테스트 샘플[2]에 대해 내 개발 머신[1]에서 이 코드를 실행하면 1시간 14분의 런타임이 발생합니다. 커피 한 잔을 들고 일어나서 스트레칭을 하거나 다른 변명을 해야 하는 시간보다 훨씬 더 많습니다. 개발자는 작업을 건너뛰는 데 사용합니다.

더 나은 접근 방식 - 트라이

이전 시나리오는 몇 가지 방법으로 향상될 수 있습니다. 예를 들어, 검색 프로세스는 여러 프로세서/코어에서 분할되고 병렬화될 수 있습니다. 그러나 이 접근 방식에 의해 달성된 런타임 감소(4개의 프로세서/코어에 대한 완벽한 분할을 가정할 때 총 런타임 20분)는 코딩/디버깅에 추가된 복잡성을 정당화하지 않습니다.

가장 좋은 해결책은 텍스트 본문을 한 번만 통과하는 것입니다. 이를 위해서는 검색 문구가 텍스트 본문과 평행하게 한 번에 선형으로 횡단될 수 있는 구조로 인덱싱되어 O(n) 의 최종 복잡성을 달성해야 합니다.

이 시나리오에만 특히 적합한 데이터 구조는 tri 입니다. 이 다재다능한 데이터 구조는 일반적으로 간과되고 검색 문제와 관련하여 다른 트리 관련 구조만큼 유명하지 않습니다.

시도에 대한 Toptal의 이전 자습서는 시도가 어떻게 구성되고 사용되는지에 대한 훌륭한 소개를 제공합니다. 간단히 말해서, 트라이는 루트에서 임의의 노드까지의 경로를 추적하여 해당 시퀀스의 유효한 하위 집합을 생성하는 방식으로 값 시퀀스를 저장할 수 있는 특수 트리입니다.

따라서 모든 검색 구를 하나의 시도로 결합할 수 있고 각 노드에는 단어가 포함되어 있으면 루트에서 아래쪽으로 모든 경로를 통해 단순히 추적하면 유효한 검색 구를 생성하는 구조로 구를 배치할 수 있습니다.

트라이의 장점은 검색 시간을 크게 단축한다는 것입니다. 이 트라이 튜토리얼의 목적을 더 쉽게 이해할 수 있도록 이진 트리를 상상해 보겠습니다. 이진 트리를 순회하는 것은 O(log 2 n) 의 복잡성을 가집니다. 각 노드가 두 개로 분기되어 나머지 순회가 반으로 줄어들기 때문입니다. 따라서 삼항 트리의 순회 복잡도는 O(log 3 n) 입니다. 그러나 시도에서 자식 노드의 수는 나타내는 순서에 따라 결정되며 읽기/의미 있는 텍스트의 경우 일반적으로 자식 노드의 수가 많습니다.

텍스트 검색 알고리즘

간단한 예로 다음과 같은 검색 구문을 가정해 보겠습니다.

• "같은 가족"
• "다른 가족"
• "별도의 존재"
• "리그 멤버들"

검색 구문을 미리 알고 있음을 기억하십시오. 따라서 우리는 시도 형태로 인덱스를 구축하는 것으로 시작합니다.

나중에 우리 소프트웨어 사용자는 다음 텍스트가 포함된 파일을 제공합니다.

유럽 ​​​​언어는 같은 가족의 구성원입니다. 그들의 별개의 존재는 신화입니다.

나머지는 아주 간단합니다. 우리 알고리즘에는 두 개의 표시기(원하는 경우 포인터)가 있습니다. 하나는 루트 또는 트리 구조의 "시작" 노드에서 시작하고 다른 하나는 텍스트 본문의 첫 번째 단어에서 시작합니다. 두 개의 지표는 단어별로 함께 움직입니다. 텍스트 표시기는 단순히 앞으로 이동하는 반면, trie 표시기는 일치하는 단어의 흔적을 따라 트리를 깊이별로 탐색합니다.

trie 표시기는 두 가지 경우에 다시 시작으로 돌아갑니다. 분기 끝에 도달했을 때(검색 구문이 발견되었음을 의미함) 또는 일치하지 않는 단어가 발견되었을 때(일치하는 항목이 없는 경우).

텍스트 표시기의 이동에 대한 한 가지 예외는 부분 일치가 발견된 경우입니다. 즉, 일련의 일치 후 분기가 끝나기 전에 일치하지 않는 항목이 발견된 경우입니다. 이 경우 마지막 단어가 새 분기의 시작일 수 있으므로 텍스트 표시기가 앞으로 이동하지 않습니다.

이 알고리즘을 우리의 tri 데이터 구조 예제에 적용하고 어떻게 되는지 봅시다.

보시다시피, 시스템은 "같은 가족" 과 "별도의 존재"라는 두 개의 일치하는 구문을 성공적으로 찾습니다.

실제 예

최근 프로젝트에서 나는 다음과 같은 문제에 직면했습니다. 클라이언트는 자신의 작업 분야와 관련된 많은 기사와 박사 학위 논문을 가지고 있으며 동일한 분야와 관련된 특정 제목과 규칙을 나타내는 문구 목록을 자신만의 목록으로 생성했습니다. 일하다.

그녀의 딜레마는 다음과 같습니다. 그녀의 문구 목록이 주어지면 기사/논문을 해당 문구에 어떻게 연결합니까? 최종 목표는 문구 그룹을 무작위로 선택하고 즉시 잡을 준비가 된 특정 문구를 언급하는 기사/논문 목록을 갖는 것입니다.

이전에 논의한 바와 같이 이 문제를 해결하는 데는 두 부분이 있습니다. 구문을 트라이로 인덱싱하는 것과 실제 검색입니다. 다음 섹션에서는 C#의 간단한 구현을 제공합니다. 파일 처리, 인코딩 문제, 텍스트 정리 및 이와 유사한 문제는 이 문서의 범위를 벗어나기 때문에 이러한 스니펫에서 처리되지 않습니다.

인덱싱

인덱싱 작업은 단순히 구문을 하나씩 순회하고 노드/레벨당 한 단어로 트리에 삽입합니다. 노드는 다음 클래스로 표시됩니다.

 class Node { int PhraseId = -1; Dictionary<String, Node> Children = new Dictionary<String, Node>(); public Node() { } public Node(int id) { PhraseId = id; } }

각 구문은 증분 숫자만큼 단순할 수 있는 ID로 표시되며 다음 인덱싱 함수에 전달됩니다(변수 루트는 트라이의 실제 루트임).

 void addPhrase(ref Node root, String phrase, int phraseId) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // break phrase into words String[] words = phrase.Split (); // start traversal at root for (int i = 0; i < words.Length; ++i) { // if the current word does not exist as a child // to current node, add it if (node.Children.ContainsKey(words[i]) == false) node.Children.Add(words[i], new Node()); // move traversal pointer to current word node = node.Children[words[i]]; // if current word is the last one, mark it with // phrase Id if (i == words.Length - 1) node.PhraseId = phraseId; } }

수색

검색 프로세스는 위의 튜토리얼에서 논의된 트라이 알고리즘을 직접 구현한 것입니다.

 void findPhrases(ref Node root, String textBody) { // a pointer to traverse the trie without damaging // the original reference Node node = root; // a list of found ids List<int> foundPhrases = new List<int>(); // break text body into words String[] words = textBody.Split (); // starting traversal at trie root and first // word in text body for (int i = 0; i < words.Length;) { // if current node has current word as a child // move both node and words pointer forward if (node.Children.ContainsKey(words[i])) { // move trie pointer forward node = node.Children[words[i]]; // move words pointer forward ++i; } else { // current node does not have current // word in its children // if there is a phrase Id, then the previous // sequence of words matched a phrase, add Id to // found list if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); if (node == root) { // if trie pointer is already at root, increment // words pointer ++i; } else { // if not, leave words pointer at current word // and return trie pointer to root node = root; } } } // one case remains, word pointer as reached the end // and the loop is over but the trie pointer is pointing to // a phrase Id if (node.PhraseId != -1) foundPhrases.Add(node.PhraseId); }

성능

여기에 제시된 코드는 실제 프로젝트에서 추출되었으며 이 문서의 목적을 위해 단순화되었습니다. 동일한 시스템[1]과 동일한 테스트 샘플[2]에서 이 코드를 다시 실행하면 트라이 빌드에 2.5초, 검색에 0.3초의 런타임이 발생했습니다. 쉬는 시간이 너무 많죠?

변형

이 트라이 튜토리얼에 설명된 알고리즘은 특정 극단적인 경우에 실패할 수 있으므로 미리 정의된 검색어를 염두에 두고 설계되었다는 점을 인식하는 것이 중요합니다.

예를 들어 다음과 같이 한 검색어의 시작 부분이 다른 검색어의 일부와 동일한 경우:

• “친구들과 공유 하고 즐기기 위해”
• “누군가와 공유할 티켓이 두 장 있습니다.”

텍스트 본문에는 다음과 같이 트라이 포인터가 잘못된 경로로 시작하도록 하는 구가 포함되어 있습니다.

친구와 공유하고 즐길 수 있는 티켓이 두 장 있습니다.

텍스트 표시기가 이미 텍스트 본문에서 일치하는 용어의 시작 부분을 통과할 때까지 trie 표시기가 시작 노드로 돌아가지 않기 때문에 알고리즘은 어떤 용어와도 일치하지 않습니다.

알고리즘을 구현하기 전에 이러한 종류의 엣지 케이스가 애플리케이션에 가능한지 여부를 고려하는 것이 중요합니다. 그렇다면 한 번에 하나의 일치만 추적하는 대신 지정된 시간에 모든 일치를 추적하도록 추가 트라이 표시기로 알고리즘을 수정할 수 있습니다.

결론

텍스트 검색은 컴퓨터 과학의 깊은 분야입니다. 문제와 솔루션이 모두 풍부한 분야. 내가 처리해야 하는 종류의 데이터(23MB의 텍스트는 실생활에서 엄청난 양의 책)는 드문 경우이거나 전문적인 문제처럼 보일 수 있지만 언어학 연구, 보관 또는 기타 유형의 데이터 조작을 다루는 개발자 , 훨씬 더 많은 양의 데이터를 정기적으로 접합니다.

위의 tri 데이터 구조 튜토리얼에서 분명히 알 수 있듯이 당면한 문제에 대한 올바른 알고리즘을 신중하게 선택하는 것이 매우 중요합니다. 이 특별한 경우에 trie 접근 방식은 런타임을 1시간 이상에서 3초 미만으로 99.93% 단축했습니다.

결코 이것이 유일한 효과적인 접근 방식은 아니지만 충분히 간단하고 작동합니다. 이 알고리즘이 흥미로웠기를 바라며 코딩 작업에서 행운을 빕니다.

[1] 이 테스트에 사용된 기계의 사양은 다음과 같습니다.

• 인텔 i7 4700HQ
• 16GB 램

테스트는 .NET 4.5.1을 사용하는 Windows 8.1과 최신 버전의 모노를 사용하는 Kubuntu 14.04에서 수행되었으며 결과는 매우 유사했습니다.

[2] 테스트 샘플은 총 23.5MB 크기의 280K 검색 구문과 1.5MB의 텍스트 본문으로 구성됩니다.