Ranking keterurutan term

Kembali menulis tentang penelitian…

Jadi pada posting-posting sebelumnya saya mengurutkan hasil pencarian (ranking) hanya dengan menghitung jumlah term (dalam hal ini trigram) yang sama antara dokumen dengan query. Semakin banyak yang sama, maka semakin tinggi rank-nya.

Namun cara seperti demikian ternyata mengandung kekurangan, yaitu trigram yang cocok pada dokumen ditemukan dalam posisi yang acak-acakan (urutannya tidak sama dengan pada query). Misalnya seperti ini (posisi trigram yang ditemukan pada dokumen) :

23, 24, 2, 3, 4, 56, 59
67, 23, 25, 5, 32, 33, 56

Terlihat bahwa trigram muncul pada posisi yang kacau, artinya sebenarnya bukan itu dokumen yang hendak dicari. Oleh karena itu, coba dicari bagaimana memberi ranking pada dokumen yang ditemukan agar yang urutannya bagus mendapat ranking yang tinggi.

Didapatkan teknik yang sesuai, yaitu mencari LIS atau longest increasing subsequence. Artinya dicari subsekuens terurut yang terpanjang dari sebuah barisan. Misalnya untuk contoh di atas:

23, 24, 2, 3, 4, 56, 59     => 2, 3, 4, 56, 59
67, 23, 25, 5, 32, 33, 56   => 23, 25, 32, 33, 56

Dengan cara ini, ranking pada suatu dokumen adalah panjang LIS dari posisi kemunculan trigram. Semakin panjang LIS-nya (yang juga artinya semakin banyak trigram yang cocok) maka ranking-nya semakin tinggi. Alhamdulillah dengan cara ini hasil pencarian menjadi lebih baik dari sebelumnya.