Mendapatkan kecocokan string terdekat

Saya perlu cara untuk membandingkan beberapa string ke string tes dan mengembalikan string yang sangat mirip:

TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW

CHOICE A   : THE RED COW JUMPED OVER THE GREEN CHICKEN
CHOICE B   : THE RED COW JUMPED OVER THE RED COW
CHOICE C   : THE RED FOX JUMPED OVER THE BROWN COW

(Jika saya melakukan ini dengan benar) String terdekat dengan "TEST STRING" harus "CHOICE C". Apa cara termudah untuk melakukan ini?

Saya berencana mengimplementasikan ini ke berbagai bahasa termasuk VB.net, Lua, dan JavaScript. Pada titik ini, kode semu dapat diterima. Jika Anda dapat memberikan contoh untuk bahasa tertentu, ini juga dihargai!

Saya dihadapkan dengan masalah ini sekitar setahun yang lalu ketika datang untuk mencari informasi yang dimasukkan pengguna tentang rig minyak dalam database informasi lain-lain. Tujuannya adalah untuk melakukan semacam pencarian string fuzzy yang dapat mengidentifikasi entri database dengan elemen yang paling umum.

Bagian dari penelitian ini melibatkan penerapan algoritma jarak Levenshtein , yang menentukan berapa banyak perubahan yang harus dilakukan pada string atau frasa untuk mengubahnya menjadi string atau frasa lain.

Implementasi yang saya buat relatif sederhana, dan melibatkan perbandingan panjang dari dua frasa, jumlah perubahan antara setiap frasa, dan apakah setiap kata dapat ditemukan dalam entri target.

Artikel ini ada di situs pribadi jadi saya akan melakukan yang terbaik untuk menambahkan konten yang relevan di sini:

Fuzzy String Matching adalah proses melakukan estimasi mirip-manusia dari kesamaan dua kata atau frasa. Dalam banyak kasus, ini melibatkan mengidentifikasi kata atau frasa yang paling mirip satu sama lain. Artikel ini menjelaskan solusi internal untuk masalah pencocokan string fuzzy dan kegunaannya dalam memecahkan berbagai masalah yang memungkinkan kita untuk mengotomatisasi tugas-tugas yang sebelumnya membutuhkan keterlibatan pengguna yang membosankan.

pengantar

Kebutuhan untuk melakukan pencocokan string fuzzy awalnya muncul saat mengembangkan alat Validator Teluk Meksiko. Apa yang ada adalah basis data jurang rig dan platform minyak Meksiko yang dikenal, dan orang-orang yang membeli asuransi akan memberi kami beberapa informasi yang diketik dengan buruk tentang aset mereka dan kami harus mencocokkannya dengan database platform yang dikenal. Ketika informasi yang diberikan sangat sedikit, yang terbaik yang bisa kami lakukan adalah mengandalkan penjamin emisi untuk "mengenali" yang mereka maksudkan dan memanggil informasi yang tepat. Di sinilah solusi otomatis ini berguna.

Saya menghabiskan satu hari meneliti metode pencocokan string fuzzy, dan akhirnya menemukan algoritma jarak Levenshtein yang sangat berguna di Wikipedia.

Penerapan

Setelah membaca tentang teori di baliknya, saya menerapkan dan menemukan cara untuk mengoptimalkannya. Ini adalah bagaimana kode saya terlihat di VBA:

'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)
Public Function LevenshteinDistance(ByRef S1 As String, ByVal S2 As String) As Long
    Dim L1 As Long, L2 As Long, D() As Long 'Length of input strings and distance matrix
    Dim i As Long, j As Long, cost As Long 'loop counters and cost of substitution for current letter
    Dim cI As Long, cD As Long, cS As Long 'cost of next Insertion, Deletion and Substitution
    L1 = Len(S1): L2 = Len(S2)
    ReDim D(0 To L1, 0 To L2)
    For i = 0 To L1: D(i, 0) = i: Next i
    For j = 0 To L2: D(0, j) = j: Next j

    For j = 1 To L2
        For i = 1 To L1
            cost = Abs(StrComp(Mid$(S1, i, 1), Mid$(S2, j, 1), vbTextCompare))
            cI = D(i - 1, j) + 1
            cD = D(i, j - 1) + 1
            cS = D(i - 1, j - 1) + cost
            If cI <= cD Then 'Insertion or Substitution
                If cI <= cS Then D(i, j) = cI Else D(i, j) = cS
            Else 'Deletion or Substitution
                If cD <= cS Then D(i, j) = cD Else D(i, j) = cS
            End If
        Next i
    Next j
    LevenshteinDistance = D(L1, L2)
End Function

Sederhana, cepat, dan metrik yang sangat berguna. Dengan menggunakan ini, saya membuat dua metrik terpisah untuk mengevaluasi kesamaan dua string. Yang saya sebut "valuePhrase" dan yang saya sebut "valueWords". valuePhrase hanyalah jarak Levenshtein antara dua frasa, dan valueWords membagi string menjadi kata-kata individual, berdasarkan pembatas seperti spasi, tanda hubung, dan apa pun yang Anda suka, dan membandingkan setiap kata dengan kata lain, meringkas setiap kata dengan kata lain, merangkum yang terpendek Jarak Levenshtein menghubungkan dua kata. Pada dasarnya, ini mengukur apakah informasi dalam satu 'frase' benar-benar terkandung dalam yang lain, sama seperti permutasi kata-bijaksana. Saya menghabiskan beberapa hari sebagai proyek sampingan dengan cara paling efisien untuk memisahkan string berdasarkan pembatas.

valueWords, valuePhrase, dan fungsi Split:

Public Function valuePhrase#(ByRef S1$, ByRef S2$)
    valuePhrase = LevenshteinDistance(S1, S2)
End Function

Public Function valueWords#(ByRef S1$, ByRef S2$)
    Dim wordsS1$(), wordsS2$()
    wordsS1 = SplitMultiDelims(S1, " _-")
    wordsS2 = SplitMultiDelims(S2, " _-")
    Dim word1%, word2%, thisD#, wordbest#
    Dim wordsTotal#
    For word1 = LBound(wordsS1) To UBound(wordsS1)
        wordbest = Len(S2)
        For word2 = LBound(wordsS2) To UBound(wordsS2)
            thisD = LevenshteinDistance(wordsS1(word1), wordsS2(word2))
            If thisD < wordbest Then wordbest = thisD
            If thisD = 0 Then GoTo foundbest
        Next word2
foundbest:
        wordsTotal = wordsTotal + wordbest
    Next word1
    valueWords = wordsTotal
End Function

''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' SplitMultiDelims
' This function splits Text into an array of substrings, each substring
' delimited by any character in DelimChars. Only a single character
' may be a delimiter between two substrings, but DelimChars may
' contain any number of delimiter characters. It returns a single element
' array containing all of text if DelimChars is empty, or a 1 or greater
' element array if the Text is successfully split into substrings.
' If IgnoreConsecutiveDelimiters is true, empty array elements will not occur.
' If Limit greater than 0, the function will only split Text into 'Limit'
' array elements or less. The last element will contain the rest of Text.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function SplitMultiDelims(ByRef Text As String, ByRef DelimChars As String, _
        Optional ByVal IgnoreConsecutiveDelimiters As Boolean = False, _
        Optional ByVal Limit As Long = -1) As String()
    Dim ElemStart As Long, N As Long, M As Long, Elements As Long
    Dim lDelims As Long, lText As Long
    Dim Arr() As String

    lText = Len(Text)
    lDelims = Len(DelimChars)
    If lDelims = 0 Or lText = 0 Or Limit = 1 Then
        ReDim Arr(0 To 0)
        Arr(0) = Text
        SplitMultiDelims = Arr
        Exit Function
    End If
    ReDim Arr(0 To IIf(Limit = -1, lText - 1, Limit))

    Elements = 0: ElemStart = 1
    For N = 1 To lText
        If InStr(DelimChars, Mid(Text, N, 1)) Then
            Arr(Elements) = Mid(Text, ElemStart, N - ElemStart)
            If IgnoreConsecutiveDelimiters Then
                If Len(Arr(Elements)) > 0 Then Elements = Elements + 1
            Else
                Elements = Elements + 1
            End If
            ElemStart = N + 1
            If Elements + 1 = Limit Then Exit For
        End If
    Next N
    'Get the last token terminated by the end of the string into the array
    If ElemStart <= lText Then Arr(Elements) = Mid(Text, ElemStart)
    'Since the end of string counts as the terminating delimiter, if the last character
    'was also a delimiter, we treat the two as consecutive, and so ignore the last elemnent
    If IgnoreConsecutiveDelimiters Then If Len(Arr(Elements)) = 0 Then Elements = Elements - 1

    ReDim Preserve Arr(0 To Elements) 'Chop off unused array elements
    SplitMultiDelims = Arr
End Function

Ukuran Kesamaan

Dengan menggunakan dua metrik ini, dan yang ketiga yang hanya menghitung jarak antara dua string, saya memiliki serangkaian variabel yang dapat saya jalankan algoritma optimasi untuk mencapai jumlah kecocokan terbanyak. Pencocokan string fuzzy, itu sendiri, adalah ilmu fuzzy, dan dengan menciptakan metrik independen linier untuk mengukur kesamaan string, dan memiliki serangkaian string yang ingin kita cocokkan satu sama lain, kita dapat menemukan parameter itu, untuk gaya spesifik kita dari string, berikan hasil pertandingan fuzzy terbaik.

Pada awalnya, tujuan metrik adalah untuk memiliki nilai pencarian yang rendah untuk kecocokan yang tepat, dan meningkatkan nilai pencarian untuk tindakan yang semakin diijinkan. Dalam kasus yang tidak praktis, ini cukup mudah untuk didefinisikan menggunakan satu set permutasi yang terdefinisi dengan baik, dan merekayasa rumus akhir sedemikian sehingga mereka telah meningkatkan hasil nilai pencarian yang diinginkan.

Pada tangkapan layar di atas, saya mengubah heuristik saya untuk menghasilkan sesuatu yang saya rasa diskalakan dengan baik untuk perbedaan persepsi saya antara istilah pencarian dan hasil. Heuristik yang saya gunakan Value Phrasedalam spreadsheet di atas adalah =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)). Saya secara efektif mengurangi penalti jarak Levenstein sebesar 80% dari perbedaan panjang dua "frasa". Dengan cara ini, "frasa" yang memiliki panjang yang sama menderita penalti penuh, tetapi "frasa" yang berisi 'informasi tambahan' (lebih lama) tetapi selain itu sebagian besar masih berbagi karakter yang sama menderita penalti berkurang. Saya menggunakan Value Wordsfungsi apa adanya, dan kemudian tugas akhir sayaSearchVal heuristik didefinisikan sebagai=MIN(D2,E2)*0.8+MAX(D2,E2)*0.2- rata-rata tertimbang. Yang mana dari dua skor yang lebih rendah mendapat bobot 80%, dan 20% dari skor yang lebih tinggi. Ini hanya heuristik yang cocok dengan kasus penggunaan saya untuk mendapatkan tingkat kecocokan yang baik. Bobot ini adalah sesuatu yang kemudian dapat diubah untuk mendapatkan tingkat kecocokan terbaik dengan data pengujian mereka.

Seperti yang Anda lihat, dua metrik terakhir, yaitu metrik pencocokan string fuzzy, sudah memiliki kecenderungan alami untuk memberikan skor rendah ke string yang dimaksudkan untuk mencocokkan (diagonal). Ini sangat bagus.

Aplikasi Untuk memungkinkan optimalisasi pencocokan fuzzy, saya menimbang setiap metrik. Dengan demikian, setiap aplikasi pencocokan string fuzzy dapat mempertimbangkan parameter secara berbeda. Formula yang mendefinisikan skor akhir adalah kombinasi sederhana dari metrik dan bobotnya:

value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight
      + Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight
      + lengthWeight*lengthValue

Menggunakan algoritme pengoptimalan (jaringan saraf terbaik di sini karena merupakan masalah diskrit, multi-dimensi), tujuannya sekarang adalah untuk memaksimalkan jumlah kecocokan. Saya membuat fungsi yang mendeteksi jumlah kecocokan yang tepat dari setiap set satu sama lain, seperti yang dapat dilihat pada tangkapan layar akhir ini. Kolom atau baris mendapat poin jika skor terendah diberikan string yang dimaksudkan untuk dicocokkan, dan poin parsial diberikan jika ada dasi untuk skor terendah, dan pertandingan yang benar adalah di antara string yang cocok yang diikat. Saya kemudian mengoptimalkannya. Anda dapat melihat bahwa sel hijau adalah kolom yang paling cocok dengan baris saat ini, dan kotak biru di sekitar sel adalah baris yang paling cocok dengan kolom saat ini. Skor di sudut bawah kira-kira adalah jumlah pertandingan yang berhasil dan inilah yang kami katakan untuk memaksimalkan masalah optimasi kami.

Algoritma itu sukses luar biasa, dan parameter solusi mengatakan banyak tentang jenis masalah ini. Anda akan melihat skor yang dioptimalkan adalah 44, dan skor terbaik yang mungkin adalah 48. 5 kolom pada akhirnya adalah umpan, dan tidak memiliki kecocokan sama sekali dengan nilai baris. Semakin banyak umpan, semakin sulit untuk menemukan pasangan yang cocok.

Dalam kasus pencocokan khusus ini, panjang string tidak relevan, karena kami mengharapkan singkatan yang mewakili kata-kata yang lebih panjang, sehingga bobot optimal untuk panjang adalah -0,3, yang berarti kami tidak menghukum string yang panjangnya bervariasi. Kami mengurangi skor untuk mengantisipasi singkatan ini, memberikan lebih banyak ruang untuk kecocokan kata parsial untuk menggantikan kecocokan non-kata yang hanya membutuhkan lebih sedikit pergantian karena string lebih pendek.

Berat kata adalah 1,0 sedangkan bobot frasa hanya 0,5, yang berarti bahwa kita menghukum seluruh kata yang hilang dari satu string dan lebih menghargai keseluruhan frase menjadi utuh. Ini berguna karena banyak string ini memiliki satu kata yang sama (bahaya) di mana yang paling penting adalah apakah kombinasi (wilayah dan bahaya) dipertahankan atau tidak.

Akhirnya, bobot minimum dioptimalkan pada 10 dan bobot maksimum pada 1. Apa artinya ini adalah bahwa jika yang terbaik dari dua skor (frasa nilai dan kata-kata nilai) tidak terlalu baik, pertandingan akan dikenakan penalti, tetapi kami tidak akan sangat menghukum yang terburuk dari dua skor. Pada dasarnya, ini menempatkan penekanan pada yang membutuhkan baik dalam valueWord atau valuePhrase memiliki skor yang baik, tapi tidak keduanya. Semacam mentalitas "ambil apa yang bisa kita dapatkan".

Benar-benar menarik apa yang dioptimalkan nilai 5 bobot ini katakan tentang jenis pencocokan string fuzzy yang terjadi. Untuk kasus praktis yang sama sekali berbeda dari pencocokan string fuzzy, parameter ini sangat berbeda. Saya telah menggunakannya untuk 3 aplikasi terpisah sejauh ini.

Meskipun tidak digunakan dalam optimisasi akhir, lembar tolok ukur dibuat yang cocok dengan kolom untuk diri mereka sendiri untuk semua hasil sempurna di diagonal, dan memungkinkan pengguna mengubah parameter untuk mengontrol tingkat di mana skor berbeda dari 0, dan perhatikan kesamaan bawaan antara frase pencarian ( yang secara teori dapat digunakan untuk mengimbangi hasil positif palsu)

Aplikasi Lebih Lanjut

Solusi ini memiliki potensi untuk digunakan di mana saja di mana pengguna ingin memiliki sistem komputer mengidentifikasi string dalam serangkaian string di mana tidak ada kecocokan yang sempurna. (Seperti perkiraan vlookup pertandingan untuk string).

Jadi apa yang harus Anda ambil dari ini, adalah bahwa Anda mungkin ingin menggunakan kombinasi heuristik tingkat tinggi (menemukan kata-kata dari satu frasa di frasa lain, panjang kedua frasa, dll) bersamaan dengan penerapan algoritma jarak Levenshtein. Karena memutuskan yang mana yang "paling cocok" adalah penentuan heuristik (kabur) - Anda harus membuat satu set bobot untuk metrik yang Anda buat untuk menentukan kesamaan.

Dengan set heuristik dan bobot yang sesuai, Anda akan memiliki program perbandingan dengan cepat membuat keputusan yang akan Anda buat.

Masalah ini muncul sepanjang waktu dalam bioinformatika. Jawaban yang diterima di atas (yang hebat dengan cara) dikenal dalam bioinformatika sebagai Needleman-Wunsch (bandingkan dua string) dan algoritma Smith-Waterman (temukan perkiraan substring dalam string yang lebih panjang). Mereka bekerja dengan baik dan telah bekerja selama puluhan tahun.

Tetapi bagaimana jika Anda memiliki sejuta string untuk dibandingkan? Itu adalah perbandingan satu triliun berpasangan, yang masing-masing adalah O (n * m)! Sequencer DNA modern dengan mudah menghasilkan satu miliar sekuens DNA pendek, masing-masing sekitar 200 "huruf" DNA. Biasanya, kami ingin menemukan, untuk setiap string tersebut, kecocokan terbaik terhadap genom manusia (3 miliar huruf). Jelas, algoritma Needleman-Wunsch dan kerabatnya tidak akan melakukannya.

Apa yang disebut "masalah pelurusan" ini adalah bidang penelitian aktif. Algoritma yang paling populer saat ini dapat menemukan kecocokan yang tidak tepat antara 1 miliar string pendek dan genom manusia dalam hitungan jam pada perangkat keras yang masuk akal (katakanlah, delapan core dan 32 GB RAM).

Sebagian besar algoritma ini bekerja dengan cepat menemukan kecocokan tepat pendek (biji) dan kemudian memperluas ini ke string penuh menggunakan algoritma yang lebih lambat (misalnya, Smith-Waterman). Alasannya adalah karena kami benar-benar hanya tertarik pada beberapa pertandingan dekat, jadi terbayar untuk menghilangkan 99,9 ...% pasangan yang tidak memiliki kesamaan.

Bagaimana cara menemukan pasangan yang tepat membantu menemukan pasangan yang tidak tepat ? Baiklah, katakanlah kami hanya mengizinkan satu perbedaan antara kueri dan target. Sangat mudah untuk melihat bahwa perbedaan ini harus terjadi di bagian kanan atau kiri dari kueri, dan setengah lainnya harus sama persis. Ide ini dapat diperluas ke beberapa ketidakcocokan dan merupakan dasar untuk algoritma ELAND yang biasa digunakan dengan sequencer DNA Illumina.

Ada banyak algoritma yang sangat baik untuk melakukan pencocokan string yang tepat. Diberikan string kueri panjang 200, dan string target panjang 3 miliar (genom manusia), kami ingin menemukan tempat di target di mana ada substring panjang k yang cocok dengan substring kueri persis. Pendekatan sederhana adalah memulai dengan mengindeks target: ambil semua substring k-long, letakkan di dalam array dan urutkan. Kemudian ambil setiap substring k-panjang dari kueri dan cari indeks yang diurutkan. Penyortiran dan pencarian dapat dilakukan dalam waktu O (log n).

Tetapi penyimpanan bisa menjadi masalah. Indeks target 3 miliar huruf perlu menampung 3 miliar petunjuk dan 3 miliar kata-k panjang. Tampaknya sulit untuk menyesuaikan ini dalam kurang dari beberapa puluh gigabyte RAM. Tapi luar biasa kita bisa sangat memadatkan indeks, menggunakan transformasi Burrows-Wheeler , dan itu masih akan efisien query. Indeks genom manusia dapat memuat kurang dari 4 GB RAM. Ide ini adalah dasar dari pelurus urutan populer seperti Bowtie dan BWA .

Sebagai alternatif, kita dapat menggunakan array sufiks , yang hanya menyimpan pointer, namun merupakan indeks simultan dari semua sufiks dalam string target (pada dasarnya, indeks simultan untuk semua nilai yang mungkin dari k; hal yang sama berlaku untuk transformasi Burrows-Wheeler ). Indeks susunan sufiks dari genom manusia akan membutuhkan RAM 12 GB jika kita menggunakan pointer 32-bit.

Tautan di atas mengandung banyak informasi dan tautan ke makalah penelitian utama. Tautan ELAND menuju ke PDF dengan angka-angka berguna yang menggambarkan konsep-konsep yang terlibat, dan menunjukkan cara menangani penyisipan dan penghapusan.

Akhirnya, sementara algoritma ini pada dasarnya memecahkan masalah (re) sekuensing genom manusia tunggal (satu miliar string pendek), teknologi sekuensing DNA meningkat lebih cepat daripada hukum Moore, dan kami dengan cepat mendekati seperangkat dataset surat. Misalnya, saat ini ada proyek yang sedang berlangsung untuk mengurutkan genom 10.000 spesies vertebrata , masing-masing sekitar satu miliar huruf. Secara alami, kami ingin melakukan pencocokan string yang tidak tepat berpasangan pada data ...

Saya berpendapat bahwa pilihan B lebih dekat dengan string uji, karena hanya 4 karakter (dan 2 dihapus) dari string asli. Sedangkan Anda melihat C lebih dekat karena itu termasuk cokelat dan merah. Namun, itu akan memiliki jarak pengeditan yang lebih besar.

Ada algoritma yang disebut Levenshtein Distance yang mengukur jarak sunting antara dua input.

Berikut adalah alat untuk algoritma itu.

1. Pilihan harga A pada jarak 15.
2. Tarif pilihan B sebagai jarak 6.
3. Pilihan tarif C sebagai jarak 9.

EDIT: Maaf, saya terus mencampur string dalam alat levenshtein. Diperbarui untuk memperbaiki jawaban.

Implementasi Lua, untuk anak cucu:

function levenshtein_distance(str1, str2)
    local len1, len2 = #str1, #str2
    local char1, char2, distance = {}, {}, {}
    str1:gsub('.', function (c) table.insert(char1, c) end)
    str2:gsub('.', function (c) table.insert(char2, c) end)
    for i = 0, len1 do distance[i] = {} end
    for i = 0, len1 do distance[i][0] = i end
    for i = 0, len2 do distance[0][i] = i end
    for i = 1, len1 do
        for j = 1, len2 do
            distance[i][j] = math.min(
                distance[i-1][j  ] + 1,
                distance[i  ][j-1] + 1,
                distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)
                )
        end
    end
    return distance[len1][len2]
end

Anda mungkin tertarik dengan postingan blog ini.

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

Fuzzywuzzy adalah pustaka Python yang menyediakan pengukuran jarak yang mudah seperti jarak Levenshtein untuk pencocokan string. Itu dibangun di atas difflib di perpustakaan standar dan akan menggunakan implementasi C Python-levenshtein jika tersedia.

http://pypi.python.org/pypi/python-Levenshtein/

Anda mungkin menemukan perpustakaan ini bermanfaat! http://code.google.com/p/google-diff-match-patch/

Saat ini tersedia dalam Java, JavaScript, Dart, C ++, C #, Objective C, Lua dan Python

Ini juga bekerja dengan sangat baik. Saya menggunakannya di beberapa proyek Lua saya.

Dan saya tidak berpikir itu akan terlalu sulit untuk port ke bahasa lain!

Jika Anda melakukan ini dalam konteks mesin pencari atau frontend terhadap database, Anda dapat mempertimbangkan untuk menggunakan alat seperti Apache Solr , dengan plugin ComplexPhraseQueryParser . Kombinasi ini memungkinkan Anda untuk mencari indeks string dengan hasil diurutkan berdasarkan relevansi, seperti yang ditentukan oleh jarak Levenshtein.

Kami telah menggunakannya melawan banyak koleksi artis dan judul lagu ketika kueri yang masuk mungkin memiliki satu atau lebih kesalahan ketik, dan itu bekerja cukup baik (dan sangat cepat mengingat koleksi berada dalam jutaan string).

Selain itu, dengan Solr, Anda dapat mencari berdasarkan indeks berdasarkan permintaan melalui JSON, sehingga Anda tidak perlu menemukan kembali solusi antara berbagai bahasa yang Anda lihat.

Sumber daya yang sangat, sangat baik untuk jenis algoritma ini adalah Simmetrics: http://sourceforge.net/projects/simmetrics/

Sayangnya situs web yang luar biasa yang berisi banyak dokumentasi hilang :( Seandainya muncul kembali, alamat sebelumnya adalah ini: http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Voila (milik "Wayback Machine"): http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Anda dapat mempelajari sumber kode, ada puluhan algoritma untuk jenis perbandingan ini, masing-masing dengan trade-off yang berbeda. Implementasinya ada di Jawa.

Untuk meminta sejumlah besar teks secara efisien, Anda dapat menggunakan konsep Edit Distance / Prefix Edit Distance.

Edit Jarak ED (x, y): jumlah transfrom minimal untuk mendapatkan dari istilah x ke istilah y

Tetapi menghitung ED antara setiap istilah dan teks permintaan adalah sumber daya dan waktu yang intensif. Karena itu, alih-alih menghitung ED untuk setiap istilah, pertama-tama kita dapat mengekstraksi kemungkinan istilah yang cocok menggunakan teknik yang disebut Indeks Qgram. dan kemudian menerapkan perhitungan ED pada persyaratan yang dipilih.

Keuntungan teknik indeks Qgram adalah mendukung untuk Pencarian Fuzzy.

Salah satu pendekatan yang mungkin untuk mengadaptasi indeks QGram adalah membangun Indeks Terbalik menggunakan Qgram. Di sana kami menyimpan semua kata yang terdiri dari Qgram tertentu, di bawah Qgram itu. (Alih-alih menyimpan string penuh, Anda dapat menggunakan ID unik untuk setiap string). Anda dapat menggunakan struktur data Peta Pohon di Jawa untuk ini. Berikut ini adalah contoh kecil tentang penyimpanan istilah

col: col mbia, col ombo, gan col a, ta col ama

Kemudian saat bertanya, kami menghitung jumlah Qgram umum antara teks kueri dan istilah yang tersedia.

Example: x = HILLARY, y = HILARI(query term)
Qgrams
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
number of q-grams in common = 4

jumlah q-gram yang sama = 4.

Untuk istilah dengan jumlah Qgram umum yang tinggi, kami menghitung ED / PED terhadap istilah kueri dan kemudian menyarankannya kepada pengguna akhir.

Anda dapat menemukan implementasi teori ini dalam proyek berikut (Lihat "QGramIndex.java"). Jangan ragu untuk bertanya. https://github.com/Bhashitha-Gamage/City_Search

Untuk mempelajari lebih lanjut tentang Edit Jarak, Awalan Edit Jarak Indeks Qgram silakan tonton video berikut dari Prof. Dr Hannah Bast https://www.youtube.com/embed/6pUg2wmGJRo (Pelajaran dimulai dari 20:06)

Masalahnya sulit diimplementasikan jika input data terlalu besar (misalkan jutaan string). Saya menggunakan pencarian elastis untuk menyelesaikan ini.

Mulai cepat: https://www.elastic.co/guide/en/elasticsearch/client/net-api/6.x/elasticsearch-net.html

Cukup masukkan semua data input ke dalam DB dan Anda dapat mencari string apa pun berdasarkan jarak edit apa pun dengan cepat. Berikut ini cuplikan C # yang akan memberi Anda daftar hasil yang diurutkan berdasarkan jarak edit (lebih kecil ke lebih tinggi)

var res = client.Search<ClassName>(s => s
    .Query(q => q
    .Match(m => m
        .Field(f => f.VariableName)
        .Query("SAMPLE QUERY")
        .Fuzziness(Fuzziness.EditDistance(5))
    )
));

Di sini Anda dapat memiliki POC golang untuk menghitung jarak antara kata-kata yang diberikan. Anda dapat menyetel minDistancedan differenceuntuk lingkup lainnya.

Taman bermain: https://play.golang.org/p/NtrBzLdC3rE

package main

import (
    "errors"
    "fmt"
    "log"
    "math"
    "strings"
)

var data string = `THE RED COW JUMPED OVER THE GREEN CHICKEN-THE RED COW JUMPED OVER THE RED COW-THE RED FOX JUMPED OVER THE BROWN COW`

const minDistance float64 = 2
const difference float64 = 1

type word struct {
    data    string
    letters map[rune]int
}

type words struct {
    words []word
}

// Print prettify the data present in word
func (w word) Print() {
    var (
        lenght int
        c      int
        i      int
        key    rune
    )
    fmt.Printf("Data: %s\n", w.data)
    lenght = len(w.letters) - 1
    c = 0
    for key, i = range w.letters {
        fmt.Printf("%s:%d", string(key), i)
        if c != lenght {
            fmt.Printf(" | ")
        }
        c++
    }
    fmt.Printf("\n")
}

func (ws words) fuzzySearch(data string) ([]word, error) {
    var (
        w      word
        err    error
        founds []word
    )
    w, err = initWord(data)
    if err != nil {
        log.Printf("Errors: %s\n", err.Error())
        return nil, err
    }
    // Iterating all the words
    for i := range ws.words {
        letters := ws.words[i].letters
        //
        var similar float64 = 0
        // Iterating the letters of the input data
        for key := range w.letters {
            if val, ok := letters[key]; ok {
                if math.Abs(float64(val-w.letters[key])) <= minDistance {
                    similar += float64(val)
                }
            }
        }

        lenSimilarity := math.Abs(similar - float64(len(data)-strings.Count(data, " ")))
        log.Printf("Comparing %s with %s i've found %f similar letter, with weight %f", data, ws.words[i].data, similar, lenSimilarity)
        if lenSimilarity <= difference {
            founds = append(founds, ws.words[i])
        }
    }

    if len(founds) == 0 {
        return nil, errors.New("no similar found for data: " + data)
    }

    return founds, nil
}

func initWords(data []string) []word {
    var (
        err   error
        words []word
        word  word
    )
    for i := range data {
        word, err = initWord(data[i])
        if err != nil {
            log.Printf("Error in index [%d] for data: %s", i, data[i])
        } else {
            words = append(words, word)
        }
    }
    return words

}

func initWord(data string) (word, error) {
    var word word

    word.data = data
    word.letters = make(map[rune]int)
    for _, r := range data {
        if r != 32 { // avoid to save the whitespace
            word.letters[r]++
        }

    }
    return word, nil
}
func main() {
    var ws words
    words := initWords(strings.Split(data, "-"))
    for i := range words {
        words[i].Print()
    }
    ws.words = words

    solution, _ := ws.fuzzySearch("THE BROWN FOX JUMPED OVER THE RED COW")
    fmt.Println("Possible solutions: ", solution)

}