Pencarian fuzzy Javascript yang masuk akal

Saya mencari pustaka JavaScript pencarian kabur untuk memfilter array. Saya sudah mencoba menggunakan fuzzyset.js dan fuse.js , tetapi hasilnya buruk (ada demo yang bisa Anda coba di halaman yang ditautkan).

Setelah melakukan beberapa membaca tentang jarak Levenshtein, menurut saya itu adalah perkiraan yang buruk tentang apa yang dicari pengguna saat mereka mengetik. Bagi mereka yang tidak tahu, sistem menghitung berapa banyak penyisipan , penghapusan , dan substitusi yang diperlukan untuk membuat dua string cocok.

Satu kekurangan yang jelas, yang diperbaiki dalam model Levenshtein-Demerau, adalah bahwa blub dan payudara dianggap sama-sama mirip dengan bulb (masing-masing membutuhkan dua substitusi). Jelas, bagaimanapun, bahwa bohlam lebih mirip dengan blub daripada payudara , dan model yang baru saya sebutkan mengakui bahwa dengan memungkinkan untuk transposisi .

Saya ingin menggunakan ini dalam konteks penyelesaian teks, jadi jika saya memiliki array ['international', 'splint', 'tinder'], dan kueri saya int , menurut saya internasional harus memiliki peringkat lebih tinggi daripada bidai , meskipun yang pertama memiliki skor (lebih tinggi = lebih buruk) 10 versus 3 yang terakhir.

Jadi yang saya cari (dan akan dibuat jika tidak ada), adalah pustaka yang melakukan hal berikut:

• Memberi bobot pada manipulasi teks yang berbeda
• Memberi bobot pada setiap manipulasi secara berbeda tergantung di mana mereka muncul dalam sebuah kata (manipulasi awal lebih mahal daripada manipulasi yang terlambat)
• Menampilkan daftar hasil yang diurutkan berdasarkan relevansi

Adakah yang pernah menemukan hal seperti ini? Saya menyadari bahwa StackOverflow bukanlah tempat untuk meminta rekomendasi perangkat lunak, tetapi implisit (tidak lagi!) Di atas adalah: apakah saya memikirkannya dengan cara yang benar?

Edit

Saya menemukan makalah yang bagus (pdf) tentang masalah ini. Beberapa catatan dan kutipan:

Fungsi Affine edit-distance menetapkan biaya yang relatif lebih rendah ke urutan penyisipan atau penghapusan

fungsi jarak Monger-Elkan (Monge & Elkan 1996), yang merupakan varian affine dari fungsi jarak Smith-Waterman (Durban et al. 1998) dengan parameter biaya tertentu

Untuk jarak Smith-Waterman (wikipedia) , "Alih-alih melihat urutan total, algoritme Smith-Waterman membandingkan segmen dari semua kemungkinan panjang dan mengoptimalkan ukuran kesamaan." Ini adalah pendekatan n-gram.

Metrik yang sangat mirip, yang tidak didasarkan pada model edit-jarak, adalah metrik Jaro (Jaro 1995; 1989; Winkler 1999). Dalam literatur record-linkage, hasil yang baik telah diperoleh dengan menggunakan varian metode ini, yang didasarkan pada jumlah dan urutan karakter umum antara dua string.

Varian ini karena Winkler (1999) juga menggunakan panjang P dari prefiks umum terpanjang

(tampaknya ditujukan terutama untuk string pendek)

Untuk tujuan pelengkapan teks, pendekatan Monger-Elkan dan Jaro-Winkler tampaknya paling masuk akal. Penambahan Winkler ke metrik Jaro secara efektif membebani awal kata dengan lebih berat. Dan aspek afinitas dari Monger-Elkan berarti bahwa kebutuhan untuk melengkapi sebuah kata (yang hanya merupakan urutan penambahan) tidak akan terlalu menyukainya.

Kesimpulan:

peringkat TFIDF berkinerja terbaik di antara beberapa metrik jarak berbasis token, dan metrik jarak edit affine-gap yang diusulkan oleh Monge dan Elkan berkinerja terbaik di antara beberapa metrik jarak edit string. Metrik jarak yang sangat bagus adalah skema heuristik cepat, yang diusulkan oleh Jaro dan kemudian diperpanjang oleh Winkler. Ini bekerja hampir sebaik skema Monge-Elkan, tetapi urutan besarnya lebih cepat. Salah satu cara sederhana untuk menggabungkan metode TFIDF dan Jaro-Winkler adalah dengan mengganti token yang sama persis yang digunakan dalam TFIDF dengan perkiraan kecocokan token berdasarkan skema Jaro-Winkler. Kombinasi ini berkinerja sedikit lebih baik daripada rata-rata Jaro-Winkler atau TFIDF, dan terkadang berkinerja jauh lebih baik. Ini juga mendekati kinerja untuk kombinasi yang dipelajari dari beberapa metrik terbaik yang dipertimbangkan dalam makalah ini.

Pertanyaan bagus! Tetapi menurut saya, daripada mencoba memodifikasi Levenshtein-Demerau, Anda mungkin lebih baik mencoba algoritma yang berbeda atau menggabungkan / menimbang hasil dari dua algoritma.

Saya terkejut bahwa kecocokan yang persis atau mirip dengan "awalan awal" adalah sesuatu yang Levenshtein-Demerau tidak memberikan bobot khusus - tetapi harapan pengguna Anda yang terlihat jelas.

Saya mencari "lebih baik dari Levenshtein" dan, antara lain, menemukan ini:

http://www.joyofdata.de/blog/comparison-of-string-distance-algorithms/

Ini menyebutkan sejumlah ukuran "jarak tali". Tiga yang terlihat sangat relevan dengan kebutuhan Anda, adalah:

1. Jarak Substring Umum Terpanjang: Jumlah minimum simbol yang harus dihapus di kedua string hingga substring yang dihasilkan identik.

2. jarak q-gram: Jumlah selisih mutlak antara vektor-vektor N-gram dari kedua string.

3. Jarak Jaccard: 1 menit hasil bagi dari N-gram bersama dan semua N-gram yang diamati.

Mungkin Anda dapat menggunakan kombinasi berbobot (atau minimum) dari metrik ini, dengan Levenshtein - substring umum, N-gram umum atau Jaccard semuanya akan sangat menyukai string yang serupa - atau mungkin mencoba hanya menggunakan Jaccard?

Bergantung pada ukuran daftar / database Anda, algoritme ini bisa jadi cukup mahal. Untuk pencarian fuzzy yang saya terapkan, saya menggunakan sejumlah N-gram yang dapat dikonfigurasi sebagai "kunci pengambilan" dari DB kemudian menjalankan pengukuran jarak string yang mahal untuk mengurutkan mereka dalam urutan preferensi.

Saya menulis beberapa catatan tentang Pencarian String Fuzzy di SQL. Lihat:

• http://literatejava.com/sql/fuzzy-string-search-sql/

Saya mencoba menggunakan pustaka fuzzy yang ada seperti fuse.js dan juga menganggapnya buruk, jadi saya menulis pustaka yang pada dasarnya berperilaku seperti pencarian luhur. https://github.com/farzher/fuzzysort

Satu-satunya kesalahan ketik yang diizinkan adalah transpos. Ini cukup solid (1k bintang, 0 masalah) , sangat cepat , dan menangani kasus Anda dengan mudah:

fuzzysort.go('int', ['international', 'splint', 'tinder'])
// [{highlighted: '*int*ernational', score: 10}, {highlighted: 'spl*int*', socre: 3003}]

Ini adalah teknik yang telah saya gunakan beberapa kali ... Ini memberikan hasil yang cukup bagus. Tidak melakukan semua yang Anda minta. Selain itu, ini bisa mahal jika daftarnya sangat besar.

get_bigrams = (string) ->
    s = string.toLowerCase()
    v = new Array(s.length - 1)
    for i in [0..v.length] by 1
        v[i] = s.slice(i, i + 2)
    return v

string_similarity = (str1, str2) ->
    if str1.length > 0 and str2.length > 0
        pairs1 = get_bigrams(str1)
        pairs2 = get_bigrams(str2)
        union = pairs1.length + pairs2.length
        hit_count = 0
        for x in pairs1
            for y in pairs2
                if x is y
                    hit_count++
        if hit_count > 0
            return ((2.0 * hit_count) / union)
    return 0.0

Berikan dua string ke string_similarity yang akan mengembalikan angka antara 0dan1.0 bergantung pada seberapa mirip mereka. Contoh ini menggunakan Lo-Dash

Contoh Penggunaan ....

query = 'jenny Jackson'
names = ['John Jackson', 'Jack Johnson', 'Jerry Smith', 'Jenny Smith']

results = []
for name in names
    relevance = string_similarity(query, name)
    obj = {name: name, relevance: relevance}
    results.push(obj)

results = _.first(_.sortBy(results, 'relevance').reverse(), 10)

console.log results

Juga .... punya biola

Pastikan konsol Anda terbuka atau Anda tidak akan melihat apa pun :)

ini adalah fungsi singkat dan ringkas saya untuk pertandingan fuzzy:

function fuzzyMatch(pattern, str) {
  pattern = '.*' + pattern.split('').join('.*') + '.*';
  const re = new RegExp(pattern);
  return re.test(str);
}

Anda dapat melihat di Atom https://github.com/atom/fuzzaldrin/ lib .

ini tersedia di npm, memiliki API sederhana, dan berfungsi dengan baik untuk saya.

> fuzzaldrin.filter(['international', 'splint', 'tinder'], 'int');
< ["international", "splint"]

Pembaruan November 2019. Saya menemukan sekering memiliki beberapa peningkatan yang lumayan. Namun, saya tidak dapat menggunakannya untuk menggunakan bool (misalnya operator OR, AND, dll) dan saya juga tidak dapat menggunakan antarmuka pencarian API untuk memfilter hasil.

Saya menemukan nextapps-de/flexsearch: https://github.com/nextapps-de/flexsearch dan saya yakin sejauh ini melampaui banyak perpustakaan pencarian javascript lain yang pernah saya coba, dan memiliki dukunganbool , memfilter pencarian & pagination.

Anda dapat memasukkan daftar objek javascript untuk data pencarian Anda (yaitu penyimpanan), dan API didokumentasikan dengan cukup baik: https://github.com/nextapps-de/flexsearch#api-overview

Sejauh ini saya telah mengindeks hampir 10.000 catatan, dan pencarian saya segera terjadi; yaitu jumlah waktu yang tidak terlalu mencolok untuk setiap penelusuran.

berikut adalah solusi yang diberikan oleh @InternalFX, tetapi di JS (saya menggunakannya begitu berbagi):

function get_bigrams(string){
  var s = string.toLowerCase()
  var v = s.split('');
  for(var i=0; i<v.length; i++){ v[i] = s.slice(i, i + 2); }
  return v;
}

function string_similarity(str1, str2){
  if(str1.length>0 && str2.length>0){
    var pairs1 = get_bigrams(str1);
    var pairs2 = get_bigrams(str2);
    var union = pairs1.length + pairs2.length;
    var hits = 0;
    for(var x=0; x<pairs1.length; x++){
      for(var y=0; y<pairs2.length; y++){
        if(pairs1[x]==pairs2[y]) hits++;
    }}
    if(hits>0) return ((2.0 * hits) / union);
  }
  return 0.0
}

Saya memperbaiki masalah dengan solusi bigram CoffeeScript oleh InternalFx dan menjadikannya solusi n-gram generik (Anda dapat menyesuaikan ukuran gram).

Ini adalah TypeScript tetapi Anda dapat menghapus anotasi tipe dan berfungsi dengan baik sebagai vanilla JavaScript juga.

/**
 * Compares the similarity between two strings using an n-gram comparison method. 
 * The grams default to length 2.
 * @param str1 The first string to compare.
 * @param str2 The second string to compare.
 * @param gramSize The size of the grams. Defaults to length 2.
 */
function stringSimilarity(str1: string, str2: string, gramSize: number = 2) {
  function getNGrams(s: string, len: number) {
    s = ' '.repeat(len - 1) + s.toLowerCase() + ' '.repeat(len - 1);
    let v = new Array(s.length - len + 1);
    for (let i = 0; i < v.length; i++) {
      v[i] = s.slice(i, i + len);
    }
    return v;
  }

  if (!str1?.length || !str2?.length) { return 0.0; }

  //Order the strings by length so the order they're passed in doesn't matter 
  //and so the smaller string's ngrams are always the ones in the set
  let s1 = str1.length < str2.length ? str1 : str2;
  let s2 = str1.length < str2.length ? str2 : str1;

  let pairs1 = getNGrams(s1, gramSize);
  let pairs2 = getNGrams(s2, gramSize);
  let set = new Set<string>(pairs1);

  let total = pairs2.length;
  let hits = 0;
  for (let item of pairs2) {
    if (set.delete(item)) {
      hits++;
    }
  }
  return hits / total;
}

Contoh:

console.log(stringSimilarity("Dog", "Dog"))
console.log(stringSimilarity("WolfmanJackIsDaBomb", "WolfmanJackIsDaBest"))
console.log(stringSimilarity("DateCreated", "CreatedDate"))
console.log(stringSimilarity("a", "b"))
console.log(stringSimilarity("CreateDt", "DateCreted"))
console.log(stringSimilarity("Phyllis", "PyllisX"))
console.log(stringSimilarity("Phyllis", "Pylhlis"))
console.log(stringSimilarity("cat", "cut"))
console.log(stringSimilarity("cat", "Cnut"))
console.log(stringSimilarity("cc", "Cccccccccccccccccccccccccccccccc"))
console.log(stringSimilarity("ab", "ababababababababababababababab"))
console.log(stringSimilarity("a whole long thing", "a"))
console.log(stringSimilarity("a", "a whole long thing"))
console.log(stringSimilarity("", "a non empty string"))
console.log(stringSimilarity(null, "a non empty string"))

Cobalah di TypeScript Playground

(function (int) {
    $("input[id=input]")
        .on("input", {
        sort: int
    }, function (e) {
        $.each(e.data.sort, function (index, value) {
          if ( value.indexOf($(e.target).val()) != -1 
              && value.charAt(0) === $(e.target).val().charAt(0) 
              && $(e.target).val().length === 3 ) {
                $("output[for=input]").val(value);
          };
          return false
        });
        return false
    });
}(["international", "splint", "tinder"]))

jsfiddle http://jsfiddle.net/guest271314/QP7z5/

Lihat add-on Google Sheets saya yang disebut Flookup dan gunakan fungsi ini:

Flookup (lookupValue, tableArray, lookupCol, indexNum, threshold, [rank])

Detail parameternya adalah:

1. lookupValue: nilai yang Anda cari
2. tableArray: tabel yang ingin Anda cari
3. lookupCol: kolom yang ingin Anda cari
4. indexNum: kolom yang datanya ingin Anda kembalikan
5. threshold: persentase kesamaan di bawah data yang seharusnya tidak dikembalikan
6. rank: pertandingan terbaik ke-n (yaitu jika pertandingan pertama tidak sesuai dengan keinginan Anda)

Ini seharusnya memenuhi kebutuhan Anda ... meskipun saya tidak yakin tentang poin nomor 2.

Cari tahu lebih lanjut di situs resminya .