Cara melaksanakan fungsi pemarkahan perkaitan untuk carian teks penuh dalam pengetahuan JavaScript_Basic

Carian teks penuh, tidak seperti kebanyakan masalah lain dalam bidang pembelajaran mesin, ialah masalah yang sering dihadapi oleh pengaturcara web dalam kerja harian mereka. Pelanggan mungkin meminta anda menyediakan kotak carian di suatu tempat, dan kemudian anda akan menulis pernyataan SQL seperti WHERE title LIKE %:query% untuk melaksanakan fungsi carian. Pada mulanya, ini tiada masalah, sehingga satu hari, pelanggan datang kepada anda dan berkata, "Terdapat ralat dalam carian!"

Sudah tentu, tiada apa yang sebenarnya "salah" dengan carian, cuma hasil carian bukanlah seperti yang pelanggan mahukan. Pengguna biasa tidak tahu cara melakukan pemadanan yang tepat, jadi hasil carian yang mereka perolehi tidak berkualiti. Untuk menyelesaikan masalah, anda memutuskan untuk menggunakan carian teks penuh. Selepas tempoh pembelajaran yang membosankan, anda mendayakan indeks FULLTEXT MySQL dan menggunakan sintaks pertanyaan yang lebih maju, seperti "MATCH() ... AGAINST()".

Okay, masalah selesai dan bunga selesai! Ini tiada masalah apabila saiz pangkalan data kecil.

Tetapi apabila anda mempunyai lebih banyak data, anda akan mendapati bahawa pangkalan data anda semakin perlahan dan perlahan. MySQL bukanlah alat carian teks penuh yang sangat mudah digunakan. Oleh itu, anda memutuskan untuk menggunakan ElasticSearch, memfaktorkan semula kod anda dan menggunakan kluster carian teks penuh berkuasa Lucene. Anda akan mendapati bahawa ia berfungsi dengan baik, pantas dan tepat.

Pada ketika ini anda pasti tertanya-tanya: Mengapa Lucene begitu hebat?

Artikel ini (terutamanya memperkenalkan TF-IDF, Okapi BM-25 dan pemarkahan perkaitan biasa) dan artikel seterusnya (terutamanya memperkenalkan pengindeksan) akan memberitahu anda konsep asas di sebalik carian teks penuh.

Perkaitan

Untuk setiap pertanyaan carian, kami dengan mudah mentakrifkan "skor kaitan" untuk setiap dokumen. Apabila pengguna mencari, kami boleh menggunakan skor perkaitan untuk mengisih dan bukannya masa penampilan dokumen. Dengan cara ini, dokumen yang paling relevan akan diletakkan pada kedudukan pertama, tidak kira berapa lama dahulu ia dicipta (sudah tentu, kadangkala ia juga berkaitan dengan masa penciptaan dokumen).

Terdapat banyak, banyak cara untuk mengira korelasi antara perkataan, tetapi kita akan mulakan dengan kaedah berasaskan statistik yang paling mudah. Kaedah ini tidak memerlukan pemahaman bahasa itu sendiri, tetapi menentukan "skor perkaitan" dengan mengira penggunaan perkataan, pemadanan dan pemberat berdasarkan kelaziman perkataan unik dalam dokumen.

Algoritma ini tidak mengambil kira sama ada perkataan itu ialah kata nama atau kata kerja, dan juga tidak mengambil berat tentang makna perkataan itu. Satu-satunya perkara yang penting ialah perkataan mana yang biasa dan mana yang jarang. Jika pertanyaan carian mengandungi kedua-dua perkataan biasa dan perkataan jarang, anda lebih baik memberikan dokumen yang mengandungi perkataan jarang itu skor yang lebih tinggi dan menurunkan berat perkataan biasa.

Algoritma ini dipanggil

Okapi BM25. Ia mengandungi dua konsep asas: kekerapan istilah (kekerapan istilah), disingkatkan sebagai kekerapan istilah ("TF") dan kekerapan dokumen songsang (disingkatkan sebagai "IDF" Jika digabungkan, ia dipanggil "TF-IDF" , iaitu ukuran statistik yang digunakan untuk menunjukkan betapa pentingnya istilah dalam dokumen.

TF-IDF

Kekerapan Jangka, atau singkatannya "TF", ialah metrik yang sangat mudah: bilangan kali perkataan tertentu muncul dalam dokumen. Anda boleh membahagikan nilai ini dengan jumlah perkataan dalam dokumen untuk mendapatkan markah. Sebagai contoh, jika terdapat 100 perkataan dalam dokumen dan perkataan 'the' muncul 8 kali, maka TF 'the' ialah 8 atau 8/100 atau 8% (bergantung pada cara anda ingin menyatakannya).

Kekerapan Dokumen Songsang, atau singkatannya "IDF", adalah sedikit lebih rumit: semakin jarang perkataan, semakin tinggi nilai ini. Ia diperoleh dengan membahagikan jumlah dokumen dengan bilangan dokumen yang mengandungi istilah, dan kemudian mengambil logaritma hasil bagi. Semakin jarang perkataan itu, semakin tinggi "IDF" yang akan dihasilkannya.

Jika anda mendarab kedua-dua nombor ini bersama-sama (TF*IDF), anda akan mendapat berat perkataan dalam dokumen. "Berat" ditakrifkan sebagai: Seberapa jarang perkataan itu dan berapa kerap ia muncul dalam dokumen?

Anda boleh menggunakan konsep ini untuk pertanyaan carian pada dokumen. Untuk setiap kata kunci dalam pertanyaan, kira skor TF-IDF mereka dan tambahkannya bersama-sama. Dokumen dengan skor tertinggi ialah dokumen yang paling sepadan dengan pernyataan pertanyaan.

Betapa hebatnya!

Okapi BM25

Algoritma di atas ialah algoritma yang boleh digunakan, tetapi ia tidak sempurna. Ia memberikan algoritma skor korelasi berasaskan statistik, yang boleh kami perbaiki lagi.

Okapi BM25 dianggap sebagai salah satu algoritma kedudukan paling maju setakat ini (oleh itu dinamakan

ElasticSearch ). Okapi BM25 menambah dua parameter boleh laras, k1 dan b, berdasarkan TF-IDF, yang masing-masing mewakili "ketepuan kekerapan jangka" dan "spesifikasi panjang medan". Apa kejadahnya ini?

Untuk memahami "ketepuan kekerapan perkataan" secara intuitif, sila bayangkan dua artikel yang sama panjang membincangkan besbol. Selain itu, mari kita anggap bahawa semua dokumen (kecuali kedua-dua ini) tidak mempunyai banyak kandungan berkaitan besbol, jadi perkataan "besbol" akan mempunyai IDF yang tinggi - ia sangat jarang berlaku dan penting. Kedua-dua artikel membincangkan besbol, dan kedua-duanya menumpukan banyak ruang untuknya, tetapi satu menggunakan perkataan "besbol" lebih daripada yang lain. Jadi dalam kes ini, adakah satu artikel benar-benar mempunyai skor yang jauh berbeza daripada artikel lain? Memandangkan kedua-dua dokumen membincangkan besbol secara meluas, tidak kira sama ada perkataan "besbol" muncul 40 kali atau 80 kali. Malah, 30 kali sepatutnya menjadi topi!

Ini ialah "ketepuan kekerapan perkataan. Algoritma TF-IDF asli tidak mempunyai konsep ketepuan, jadi dokumen dengan "besbol" muncul 80 kali mempunyai skor dua kali lebih tinggi daripada yang muncul 40 kali. Kadang-kadang, inilah yang kita mahukan, tetapi Kadang-kadang kita tidak mahu itu

Selain itu, Okapi BM25 juga mempunyai parameter k1, yang digunakan untuk melaraskan kadar perubahan tepu. Nilai parameter k1 biasanya antara 1.2 dan 2.0. Semakin rendah nilai, semakin cepat proses tepu. (maksudnya kedua-dua dokumen di atas mempunyai markah yang sama kerana kedua-duanya mengandungi banyak perkataan "besbol")

Penormalan panjang medan mengurangkan panjang dokumen kepada purata panjang semua dokumen. Ini berguna untuk koleksi satu medan (seperti kami), untuk menyatukan dokumen dengan panjang yang berbeza kepada kriteria perbandingan yang sama. Ia lebih masuk akal untuk koleksi dua medan (seperti "tajuk" dan "badan"), yang turut menyatukan medan tajuk dan isi kepada kriteria perbandingan yang sama. Pengurangan panjang medan diwakili oleh b, yang mempunyai nilai antara 0 dan 1, dengan 1 bermakna pengurangan penuh dan 0 bermakna tiada pengurangan.

Algoritma

Anda boleh belajar tentang formula algoritma Okapi dalam

Okapi BM25 Wikipedia . Sekarang kita tahu apa setiap istilah dalam formula, ia mesti mudah difahami. Oleh itu, jangan sebut formula dan pergi terus ke kod:

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;
};

Kami mentakrifkan kaedah statik mudah Tokenize() untuk menghuraikan rentetan ke dalam tatasusunan token. Itu sahaja, kita huruf kecil semua token (untuk mengurangkan entropi). Kami menjalankan algoritma Porter Stemmer untuk mengurangkan jumlah entropi sambil meningkatkan tahap padanan ("berjalan" dan "berjalan" padanan adalah sama). Dan kami juga menapis kata henti (perkataan yang sangat biasa) untuk mengurangkan lagi entropi. Sebelum saya terlalu mendalami konsep yang saya tulis, harap bersabar jika saya terlalu menerangkan bahagian ini.

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;
};

Di sinilah kaedah addDocument() muncul secara ajaib. Kami pada asasnya membina dan mengekalkan dua struktur data yang serupa: this.documents dan this.terms.

This.documentsis ialah pangkalan data yang menyimpan semua dokumen Ia menyimpan semua teks asal dokumen, maklumat panjang dokumen dan senarai yang menyimpan semua perkataan dalam dokumen dan bilangan serta kekerapan kejadian. perkataan. Menggunakan struktur data ini, kita boleh menjawab soalan berikut dengan mudah dan cepat (ya, sangat pantas, hanya memerlukan masa pertanyaan jadual cincang O(1) kerumitan masa): Dalam dokumen #3, 'berjalan' ini Berapa kali perkataan muncul?

Kami juga menggunakan struktur data lain, this.terms. Ia mewakili semua perkataan dalam korpus. Melalui struktur data ini, kita boleh menjawab soalan berikut dalam masa O(1): Berapa banyak dokumen yang terdapat dalam perkataan 'berjalan'? Apakah id mereka?

Akhir sekali, kami merekodkan panjang setiap dokumen dan merekodkan purata panjang dokumen merentas keseluruhan korpus.

Ambil perhatian bahawa dalam kod di atas, idf dimulakan kepada 0 dan kaedah updateidf() diulas. Ini kerana kaedah ini berjalan sangat perlahan dan hanya perlu dijalankan sekali sahaja, selepas pengindeksan. Memandangkan menjalankannya sekali boleh memenuhi keperluan, tidak perlu menjalankannya 5,000 kali. Mengulasnya dahulu dan menjalankannya selepas kumpulan besar operasi pengindeksan boleh menjimatkan banyak masa. Berikut ialah kod untuk fungsi ini:

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);
  }
};

Ini adalah fungsi yang sangat mudah, tetapi kerana ia perlu merentasi semua perkataan dalam keseluruhan korpus dan mengemas kini nilai semua perkataan, ia berfungsi agak perlahan. Kaedah ini dilaksanakan menggunakan formula standard untuk kekerapan dokumen songsang (anda boleh mencari formula ini di Wikipedia) - bahagikan jumlah bilangan dokumen dengan bilangan dokumen yang mengandungi perkataan, dan kemudian ambil logaritma hasil hasil. Saya membuat beberapa pengubahsuaian supaya nilai pulangan sentiasa lebih besar daripada 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);
};

Akhir sekali, kaedah carian() merentasi semua dokumen dan memberikan skor BM25 bagi setiap dokumen, dan kemudian mengisihnya dalam tertib menurun. Sudah tentu, adalah tidak bijak untuk menyemak setiap dokumen dalam korpus semasa carian. Isu ini ditangani dalam Bahagian Dua (Indeks dan Prestasi Terbalik).

Kod di atas diulas dengan baik dan intipatinya adalah seperti berikut: Kira skor BM25 untuk setiap dokumen dan setiap perkataan. Skor idf perkataan telah dikira terlebih dahulu, dan anda hanya perlu menanyakannya apabila menggunakannya. Kekerapan perkataan juga diprakira sebagai sebahagian daripada sifat dokumen. Selepas itu, hanya empat operasi aritmetik mudah diperlukan. Akhir sekali, tambahkan pembolehubah sementara _skor pada setiap dokumen, kemudian isikannya dalam susunan menurun mengikut skor dan kembalikan 10 keputusan teratas.
Contoh, kod sumber, nota dan langkah seterusnya

Terdapat banyak cara untuk mengoptimumkan contoh di atas, kami akan memperkenalkannya di bahagian kedua "Carian Teks Penuh", sila nantikan. Saya harap saya dapat menyelesaikannya dalam beberapa minggu. Di bawah ialah senarai perkara yang akan disebut pada masa akan datang:

• Indeks songsang dan carian pantas
• Indeks pantas
• Hasil carian yang lebih baik

Untuk demonstrasi ini, saya menulis perangkak Wikipedia kecil yang merangkak ke perenggan pertama daripada beberapa (85,000) rencana Wikipedia. Memandangkan mengindeks semua 85K fail mengambil masa kira-kira 90 saat, pada komputer saya, saya telah memotongnya separuh. Saya tidak mahu anda membazirkan kuasa komputer riba anda hanya untuk pembentangan teks penuh ringkas.

Oleh kerana pengindeksan ialah operasi CPU modular yang berat, saya menganggapnya sebagai pekerja rangkaian. Pengindeksan dijalankan pada urutan latar belakang --Anda boleh mencari kod sumber penuh di sini. Anda juga akan menemui rujukan kod sumber kepada algoritma stemming dan senarai kata henti saya. Bagi lesen kod, ia masih percuma untuk tujuan pendidikan dan bukan untuk sebarang tujuan komersial.

Akhir sekali, demo. Setelah indeks selesai, cuba cari perkara dan frasa rawak dan Wikipedia akan mengetahuinya. Ambil perhatian bahawa terdapat hanya 40,000 segmen yang diindeks, jadi anda mungkin ingin mencuba beberapa topik baharu.