전체 텍스트 검색은 기계 학습 분야의 다른 대부분의 문제와 달리 웹 프로그래머가 일상 작업에서 자주 직면하는 문제입니다. 고객이 어딘가에 검색 상자를 제공하도록 요청할 수 있으며 WHERE title LIKE %:query%와 같은 SQL 문을 작성하여 검색 기능을 구현합니다. 처음에는 아무 문제가 없었는데, 어느 날 고객이 찾아와서 "검색에 오류가 생겼어요!"라고 하더군요.
물론 검색에 실제로 '잘못'된 것은 없으며 단지 검색 결과가 고객이 원하는 것과 다를 뿐입니다. 일반 사용자는 정확한 일치를 수행하는 방법을 모르기 때문에 얻는 검색 결과의 품질이 좋지 않습니다. 문제를 해결하기 위해 전체 텍스트 검색을 사용하기로 결정했습니다. 지루한 학습 기간을 보낸 후 MySQL의 FULLTEXT 인덱스를 활성화하고 "MATCH() ... AGAINST()"와 같은 고급 쿼리 구문을 사용했습니다.
자, 문제가 해결되고 꽃이 완성되었습니다! 데이터베이스 크기가 작은 경우에는 문제가 되지 않습니다.
그러나 데이터가 점점 더 많아지면 데이터베이스가 점점 느려지는 것을 알게 될 것입니다. MySQL은 사용하기 쉬운 전체 텍스트 검색 도구가 아닙니다. 따라서 ElasticSearch를 사용하고, 코드를 리팩터링하고, Lucene 기반 전체 텍스트 검색 클러스터를 배포하기로 결정했습니다. 당신은 그것이 매우 잘 작동하고 빠르고 정확하게 작동한다는 것을 알게 될 것입니다.
이 시점에서 궁금하지 않을 수 없습니다. Lucene이 왜 그렇게 멋진가요?
이 기사(주로 TF-IDF, Okapi BM-25 및 일반 관련성 점수 소개)와 다음 기사(주로 인덱싱 소개)에서는 전체 텍스트 검색의 기본 개념을 설명합니다.
관련성
각 검색어에 대해 각 문서의 '관련성 점수'를 쉽게 정의합니다. 사용자가 검색할 때 문서 출현 시간 대신 관련성 점수를 사용하여 정렬할 수 있습니다. 이렇게 하면 생성된 지 얼마나 되었는지에 관계없이 가장 관련성이 높은 문서가 첫 번째 순위가 됩니다(물론 문서 생성 시간과도 관련이 있는 경우도 있습니다).
단어 간의 상관관계를 계산하는 방법은 매우 많지만 가장 간단한 통계 기반 방법부터 시작하겠습니다. 이 방법은 언어 자체에 대한 이해가 필요하지 않고, 문서 내 고유 단어의 출현율을 기준으로 단어 사용, 일치, 가중치를 계산하여 "관련성 점수"를 결정합니다.
이 알고리즘은 단어가 명사인지 동사인지 상관하지 않으며 단어의 의미에도 신경 쓰지 않습니다. 그것이 관심을 갖는 유일한 것은 어떤 단어가 흔한지, 어떤 단어가 희귀한지입니다. 검색 쿼리에 일반적인 단어와 희귀한 단어가 모두 포함된 경우 희귀한 단어가 포함된 문서에 더 높은 점수를 부여하고 일반적인 단어의 가중치를 낮추는 것이 좋습니다.
이 알고리즘의 이름은 Okapi BM25입니다. 여기에는 2가지 기본 개념이 포함되어 있습니다. 용어 빈도("TF")로 약칭하는 용어 빈도와 역문서 빈도("IDF"로 약칭)를 합쳐서 "TF-IDF"라고 합니다. 문서에서 용어의 중요성을 나타내는 데 사용되는 통계적 척도입니다.
TF-IDF
용어 빈도, 줄여서 'TF'는 매우 간단한 측정 기준입니다. 즉, 특정 단어가 문서에 나타나는 횟수입니다. 이 값을 문서의 총 단어 수로 나누어 점수를 얻을 수 있습니다. 예를 들어 문서에 100개의 단어가 있고 'the'라는 단어가 8번 나타나면 'the'의 TF는 8, 8/100 또는 8%(표현하려는 방식에 따라 다름)입니다.
역문서 빈도(Inverse Document Frequency), 줄여서 "IDF"는 조금 더 복잡합니다. 단어가 희귀할수록 이 값이 높아집니다. 전체 문서 수를 해당 용어가 포함된 문서 수로 나눈 다음 몫에 로그를 취하여 구합니다. 단어가 희귀할수록 생성되는 "IDF"가 높아집니다.
이 두 숫자를 곱하면(TF*IDF) 문서에서 단어의 무게를 얻게 됩니다. "무게"는 다음과 같이 정의됩니다. 해당 단어가 얼마나 드물고 문서에 얼마나 자주 등장합니까?
문서에 대한 검색어에 이 개념을 사용할 수 있습니다. 쿼리의 각 키워드에 대해 TF-IDF 점수를 계산하고 이를 합산합니다. 점수가 가장 높은 문서가 쿼리문과 가장 잘 일치하는 문서입니다.
멋지네요!
오카피 BM25
위 알고리즘은 사용 가능한 알고리즘이지만 완벽하지는 않습니다. 이는 통계 기반의 상관 점수 알고리즘을 제공하며 이를 더욱 개선할 수 있습니다.
Okapi BM25는 지금까지 가장 발전된 순위 알고리즘 중 하나로 간주됩니다(그래서 ElasticSearch라는 이름이 붙었습니다). Okapi BM25는 TF-IDF를 기반으로 각각 "용어 주파수 포화도"와 "필드 길이 사양"을 나타내는 두 개의 조정 가능한 매개변수 k1과 b를 추가합니다. 이게 대체 뭐야?
'단어 빈도 포화도'를 직관적으로 이해하려면 야구를 다룬 비슷한 길이의 두 기사를 상상해 보세요. 또한 이 두 문서를 제외한 모든 문서에 야구 관련 콘텐츠가 많지 않다고 가정해 보겠습니다. 따라서 "야구"라는 단어는 높은 IDF를 갖게 됩니다. 이는 매우 드물고 중요합니다. 두 기사 모두 야구에 대해 다루고 있으며 둘 다 상당한 공간을 할애하고 있지만 한 기사는 다른 기사보다 "야구"라는 단어를 더 많이 사용합니다. 그렇다면 이 경우 실제로 한 기사가 다른 기사와 점수가 많이 다른가요? 두 문서 모두 야구를 전반적으로 다루고 있기 때문에 '야구'라는 단어가 40번 나오든, 80번 나오든 상관없습니다. 사실, 30번이 상한선이어야 합니다!
이것이 "단어 빈도 포화도"입니다. 기본 TF-IDF 알고리즘에는 포화 개념이 없으므로 "야구"가 80번 나타나는 문서는 40번 나타나는 문서보다 두 배 높은 점수를 갖습니다. 때로는 이것이 우리가 원하는 것입니다. 하지만 때때로 우리는 그것을 원하지 않습니다.
또한 Okapi BM25에는 채도 변화율을 조정하는 데 사용되는 k1 매개변수도 있습니다. k1 매개변수의 값은 일반적으로 1.2에서 2.0 사이입니다. 값이 낮을수록 포화 프로세스가 더 빨라집니다. (위의 두 문서에는 "야구"라는 단어가 많이 포함되어 있으므로 점수가 동일하다는 의미)
필드 길이 정규화는 문서 길이를 모든 문서의 평균 길이로 줄입니다. 이는 단일 필드 컬렉션(예: 우리 컬렉션)에서 길이가 다른 문서를 동일한 비교 기준으로 통합하는 데 유용합니다. 이는 제목과 본문 필드를 동일한 비교 기준으로 통합하는 2개 필드 컬렉션(예: "제목" 및 "본문")에 더 적합합니다. 필드 길이 감소는 b로 표시되며, 이는 0과 1 사이의 값을 가지며, 1은 전체 감소를 의미하고 0은 감소 없음을 의미합니다.
알고리즘
Okapi 알고리즘의 공식은 Okapi BM25 Wikipedia에서 알아볼 수 있습니다. 이제 공식의 각 용어가 무엇인지 알았으니 이해하기 쉬울 것입니다. 그러니 수식은 언급하지 말고 바로 코드로 넘어가겠습니다.
BM25.Tokenize = function(text) {
text = text
.toLowerCase()
.replace(/\W/g, ' ')
.replace(/\s+/g, ' ')
.trim()
.split(' ')
.map(function(a) { return stemmer(a); });
// Filter out stopStems
var out = [];
for (var i = 0, len = text.length; i < len; i++) {
if (stopStems.indexOf(text[i]) === -1) {
out.push(text[i]);
}
}
return out;
};
문자열을 토큰 배열로 구문 분석하는 간단한 정적 메소드 Tokenize()를 정의합니다. 엔트로피를 줄이기 위해 모든 토큰을 소문자로 표현합니다. 우리는 엔트로피의 양을 줄이는 동시에 일치 정도를 향상시키기 위해 Porter Stemmer 알고리즘을 실행합니다("걷기"와 "걷기" 일치는 동일함). 또한 엔트로피를 더욱 줄이기 위해 불용어(매우 일반적인 단어)를 필터링합니다. 제가 쓴 개념에 너무 깊이 들어가기 전에, 이 섹션을 과도하게 설명하더라도 양해해 주시기 바랍니다.
BM25.prototype.addDocument = function(doc) {
if (typeof doc.id === 'undefined') { throw new Error(1000, 'ID is a required property of documents.'); };
if (typeof doc.body === 'undefined') { throw new Error(1001, 'Body is a required property of documents.'); };
// Raw tokenized list of words
var tokens = BM25.Tokenize(doc.body);
// Will hold unique terms and their counts and frequencies
var _terms = {};
// docObj will eventually be added to the documents database
var docObj = {id: doc.id, tokens: tokens, body: doc.body};
// Count number of terms
docObj.termCount = tokens.length;
// Increment totalDocuments
this.totalDocuments++;
// Readjust averageDocumentLength
this.totalDocumentTermLength += docObj.termCount;
this.averageDocumentLength = this.totalDocumentTermLength / this.totalDocuments;
// Calculate term frequency
// First get terms count
for (var i = 0, len = tokens.length; i < len; i++) {
var term = tokens[i];
if (!_terms[term]) {
_terms[term] = {
count: 0,
freq: 0
};
};
_terms[term].count++;
}
// Then re-loop to calculate term frequency.
// We'll also update inverse document frequencies here.
var keys = Object.keys(_terms);
for (var i = 0, len = keys.length; i < len; i++) {
var term = keys[i];
// Term Frequency for this document.
_terms[term].freq = _terms[term].count / docObj.termCount;
// Inverse Document Frequency initialization
if (!this.terms[term]) {
this.terms[term] = {
n: 0, // Number of docs this term appears in, uniquely
idf: 0
};
}
this.terms[term].n++;
};
// Calculate inverse document frequencies
// This is SLOWish so if you want to index a big batch of documents,
// comment this out and run it once at the end of your addDocuments run
// If you're only indexing a document or two at a time you can leave this in.
// this.updateIdf();
// Add docObj to docs db
docObj.terms = _terms;
this.documents[docObj.id] = docObj;
};
여기서 addDocument() 메소드가 마술처럼 나타납니다. 우리는 기본적으로 this.documents와 this.terms라는 두 가지 유사한 데이터 구조를 구축하고 유지합니다.
This.documentssis는 모든 문서를 저장하는 데이터베이스입니다. 문서의 모든 원본 텍스트와 문서의 길이 정보, 문서의 모든 단어와 발생 빈도를 저장하는 목록을 저장합니다. 단어. 이 데이터 구조를 사용하면 다음 질문에 쉽고 빠르게 답할 수 있습니다(예, 매우 빠르며 O(1) 시간 복잡도의 해시 테이블 쿼리 시간만 필요함). 문서 #3에서 'walk' this는 몇 번이나 수행됩니까? 말이 나오나요?
또 다른 데이터 구조인 this.terms도 사용합니다. 말뭉치의 모든 단어를 나타냅니다. 이 데이터 구조를 통해 O(1) 시간 내에 다음 질문에 답할 수 있습니다. 'walk'라는 단어가 몇 개의 문서에 나타납니까? 그 사람의 아이디는 무엇인가요?
마지막으로 각 문서의 길이를 기록하고 전체 말뭉치에 걸쳐 문서의 평균 길이를 기록합니다.
위 코드에서 idf는 0으로 초기화되고 updateidf() 메서드는 주석 처리되어 있습니다. 이는 이 방법이 매우 느리게 실행되고 인덱싱 후 한 번만 실행하면 되기 때문입니다. 한 번 실행하면 요구 사항을 충족할 수 있으므로 5,000번 실행할 필요가 없습니다. 먼저 주석 처리하고 대규모 인덱싱 작업 후에 실행하면 많은 시간을 절약할 수 있습니다. 이 함수의 코드는 다음과 같습니다.
BM25.prototype.updateIdf = function() {
var keys = Object.keys(this.terms);
for (var i = 0, len = keys.length; i < len; i++) {
var term = keys[i];
var num = (this.totalDocuments - this.terms[term].n + 0.5);
var denom = (this.terms[term].n + 0.5);
this.terms[term].idf = Math.max(Math.log10(num / denom), 0.01);
}
};
아주 간단한 기능이지만 전체 말뭉치의 모든 단어를 순회하고 모든 단어의 값을 업데이트해야 하기 때문에 작동이 조금 느립니다. 이 방법은 역 문서 빈도에 대한 표준 공식을 사용하여 구현됩니다(이 공식은 Wikipedia에서 찾을 수 있음). 전체 문서 수를 단어가 포함된 문서 수로 나눈 다음 몫의 로그를 취합니다. 반환 값이 항상 0보다 크도록 일부 수정했습니다.
BM25.prototype.search = function(query) {
var queryTerms = BM25.Tokenize(query);
var results = [];
// Look at each document in turn. There are better ways to do this with inverted indices.
var keys = Object.keys(this.documents);
for (var j = 0, nDocs = keys.length; j < nDocs; j++) {
var id = keys[j];
// The relevance score for a document is the sum of a tf-idf-like
// calculation for each query term.
this.documents[id]._score = 0;
// Calculate the score for each query term
for (var i = 0, len = queryTerms.length; i < len; i++) {
var queryTerm = queryTerms[i];
// We've never seen this term before so IDF will be 0.
// Means we can skip the whole term, it adds nothing to the score
// and isn't in any document.
if (typeof this.terms[queryTerm] === 'undefined') {
continue;
}
// This term isn't in the document, so the TF portion is 0 and this
// term contributes nothing to the search score.
if (typeof this.documents[id].terms[queryTerm] === 'undefined') {
continue;
}
// The term is in the document, let's go.
// The whole term is :
// IDF * (TF * (k1 + 1)) / (TF + k1 * (1 - b + b * docLength / avgDocLength))
// IDF is pre-calculated for the whole docset.
var idf = this.terms[queryTerm].idf;
// Numerator of the TF portion.
var num = this.documents[id].terms[queryTerm].count * (this.k1 + 1);
// Denomerator of the TF portion.
var denom = this.documents[id].terms[queryTerm].count
+ (this.k1 * (1 - this.b + (this.b * this.documents[id].termCount / this.averageDocumentLength)));
// Add this query term to the score
this.documents[id]._score += idf * num / denom;
}
if (!isNaN(this.documents[id]._score) && this.documents[id]._score > 0) {
results.push(this.documents[id]);
}
}
results.sort(function(a, b) { return b._score - a._score; });
return results.slice(0, 10);
};
마지막으로 search() 메서드는 모든 문서를 순회하여 각 문서의 BM25 점수를 제공한 다음 내림차순으로 정렬합니다. 물론, 검색하는 동안 말뭉치의 모든 문서를 살펴보는 것은 현명하지 못할 것입니다. 이 문제는 2부(역 인덱스 및 성능)에서 해결됩니다.
위의 코드는 주석이 잘 되어 있으며 그 요지는 다음과 같습니다. 각 문서와 단어별로 BM25 점수를 계산합니다. 해당 단어의 idf 점수가 미리 계산되어 있어, 사용시에만 쿼리하면 됩니다. 단어 빈도는 문서 속성의 일부로 미리 계산됩니다. 그 후에는 네 가지 간단한 산술 연산만 필요합니다. 마지막으로 각 문서에 임시 변수 _score를 추가한 다음 점수에 따라 내림차순으로 정렬하고 상위 10개 결과를 반환합니다.
예제, 소스 코드, 참고 사항 및 다음 단계
위의 예를 최적화하는 방법은 여러 가지가 있습니다. "전체 텍스트 검색"의 두 번째 부분에서 소개하겠습니다. 계속 지켜봐 주시기 바랍니다. 몇 주 안에 끝낼 수 있었으면 좋겠습니다. 다음에 언급할 내용은 다음과 같습니다.
이 데모를 위해 저는 꽤 많은(85,000개) Wikipedia 기사의 첫 번째 단락을 크롤링하는 작은 Wikipedia 크롤러를 작성했습니다. 85,000개 파일을 모두 인덱싱하는 데 약 90초가 걸리기 때문에 내 컴퓨터에서는 이 시간을 절반으로 줄였습니다. 단지 간단한 전체 텍스트 프레젠테이션을 위해 노트북 전원을 낭비하지 않기를 바랍니다.
인덱싱은 무거운 모듈식 CPU 작업이므로 네트워크 작업자로 취급합니다. 인덱싱은 백그라운드 스레드에서 실행됩니다. --여기에서 전체 소스 코드를 찾을 수 있습니다. 또한 형태소 분석 알고리즘과 불용어 목록에 대한 소스 코드 참조도 찾을 수 있습니다. 코드 라이센스는 여전히 교육 목적으로 무료이며 상업적 목적으로는 무료입니다.
마지막으로 데모입니다. 색인이 완성되면 임의의 항목과 문구를 찾아보세요. 그러면 Wikipedia가 이에 대해 알게 됩니다. 색인이 생성된 세그먼트는 40,000개뿐이므로 새로운 주제를 시도해 볼 수도 있습니다.
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
