Berapa panjang senar Anda?
Jika mereka relatif pendek (misalnya kata-kata bahasa Inggris; avg_len=5) dan Anda memiliki penyimpanan basis data, coba pendekatan ini:
- Untuk setiap kata yang ingin Anda simpan dalam tabel, ambil setiap akhiran kata yang mungkin. Dengan kata lain, Anda terus menghapus karakter pertama sampai tidak ada yang tersisa. Misalnya, kata
valuememberikan:valuealuelueuee
- Simpan setiap sufiks ini dalam database.
- Sekarang Anda dapat mencari substring menggunakan
LIKE 'alu%'(yang akan menemukan 'alu' sebagai bagian dari 'nilai').
Dengan menyimpan semua sufiks, Anda telah menghilangkan kebutuhan akan wildcard terdepan (memungkinkan indeks digunakan untuk pencarian cepat), dengan mengorbankan ruang penyimpanan.
Biaya Penyimpanan
Jumlah karakter yang diperlukan untuk menyimpan sebuah kata menjadi word_len*word_len / 2 , yaitu kuadrat dalam panjang kata, berdasarkan per kata. Berikut adalah faktor peningkatan untuk berbagai ukuran kata:
- Kata 3 huruf:
(3*3/2) / 3 = 1.5 - Kata 5 huruf:
(5*5/2) / 5 = 2.5 - Kata 7 huruf:
(7*7/2) / 7 = 3.5 - Kata 12 huruf:
(12*12/2) / 12 = 6
Jumlah baris yang diperlukan untuk menyimpan kata meningkat dari 1 menjadi word_len . Berhati-hatilah dengan overhead ini. Kolom tambahan harus dijaga seminimal mungkin untuk menghindari penyimpanan data yang berlebihan dalam jumlah besar. Misalnya, nomor halaman di mana kata itu awalnya ditemukan harus baik-baik saja (pikirkan smallint yang tidak ditandatangani), tetapi metadata ekstensif pada kata tersebut harus disimpan dalam tabel terpisah berdasarkan per kata, bukan untuk setiap sufiks.
Pertimbangan
Ada trade-off di mana kita membagi 'kata-kata' (atau fragmen). Sebagai contoh dunia nyata:apa yang kita lakukan dengan tanda hubung? Apakah kita menyimpan kata sifat five-letter sebagai satu atau dua kata?
Pertukarannya adalah sebagai berikut:
- Apa pun yang dipecah tidak dapat ditemukan sebagai satu elemen. Jika kita menyimpan
fivedanlettersecara terpisah, mencarifive-letterataufiveletterakan gagal. - Apa pun yang bukan putus akan memakan lebih banyak ruang penyimpanan. Ingat, persyaratan penyimpanan meningkat secara kuadrat dalam panjang kata.
Untuk kenyamanan, Anda mungkin ingin menghapus tanda hubung dan menyimpan fiveletter . Kata tersebut sekarang dapat ditemukan dengan mencari five , letter , dan fiveletter . (Jika Anda juga menghapus tanda hubung dari kueri penelusuran apa pun, pengguna masih dapat berhasil menemukan five-letter .)
Terakhir, ada cara untuk menyimpan array sufiks yang tidak memerlukan banyak overhead, tetapi saya belum yakin apakah mereka dapat menerjemahkan dengan baik ke database.
