Struktur Data Trie: Permata yang Diabaikan

Sejak hari pertama dalam hidup kita sebagai programmer, kita semua telah berurusan dengan struktur data: Array, linked list, tree, set, stack, dan antrian adalah teman sehari-hari kita, dan programmer berpengalaman tahu kapan dan mengapa menggunakannya. Dalam artikel ini kita akan melihat bagaimana struktur data yang sering diabaikan, trie , benar-benar bersinar di domain aplikasi dengan fitur khusus, seperti permainan kata.

Permainan Kata sebagai Contoh Trie

Sebagai permulaan, mari kita pertimbangkan teka-teki kata sederhana: temukan semua kata yang valid di papan huruf 4x4, menghubungkan huruf-huruf yang berdekatan secara horizontal, vertikal, atau diagonal. Sebagai contoh, di papan berikut, kita melihat huruf 'W', 'A', 'I', dan 'T' terhubung membentuk kata "WAIT".

Solusi naif untuk menemukan semua kata yang valid adalah dengan menjelajahi papan mulai dari sudut kiri atas dan kemudian memindahkan kedalaman-pertama ke urutan yang lebih panjang, mulai lagi dari huruf kedua di baris pertama, dan seterusnya. Dalam papan 4x4, memungkinkan gerakan vertikal, horizontal dan diagonal, ada 12029640 urutan, mulai dari satu hingga enam belas karakter.

Sekarang, tujuan kami adalah menemukan struktur data terbaik untuk menerapkan pemeriksa kata yang valid ini, yaitu kosakata kami. Beberapa poin yang perlu diingat:

• Kami hanya membutuhkan satu salinan dari setiap kata, yaitu, kosa kata kami adalah satu set, dari sudut pandang logis.
• Kita perlu menjawab pertanyaan-pertanyaan berikut untuk setiap kata yang diberikan:
  • Apakah urutan karakter saat ini terdiri dari kata yang valid?
  • Apakah ada kata yang lebih panjang yang dimulai dengan urutan ini? Jika tidak, kita dapat meninggalkan eksplorasi mendalam-pertama kita, karena masuk lebih dalam tidak akan menghasilkan kata-kata yang valid.

Untuk mengilustrasikan poin kedua, perhatikan papan berikut: Tidak ada gunanya mengeksplorasi gerakan selanjutnya, karena tidak ada kata dalam kamus yang dimulai dengan “ASF”.

Kami ingin struktur data kami menjawab pertanyaan ini secepat mungkin. ~O(1) waktu akses (untuk memeriksa urutan) akan ideal!

Kita dapat mendefinisikan antarmuka Kosakata seperti ini (lihat di sini untuk repo GitHub):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Struktur Data Trie vs. Alternatif

Menerapkan metode contains() memerlukan struktur data pendukung yang memungkinkan Anda menemukan elemen secara efisien, sedangkan metode isPrefix() mengharuskan kita untuk menemukan "elemen yang lebih besar berikutnya", yaitu kita perlu menjaga kosa kata diurutkan dalam beberapa cara.

Kami dapat dengan mudah mengecualikan set berbasis hash dari daftar kandidat kami: sementara struktur seperti itu akan memberi kami pemeriksaan waktu konstan untuk contain( contains() , itu akan berkinerja sangat buruk pada isPrefix() , dalam kasus terburuk mengharuskan kami memindai keseluruhan mengatur.

Untuk alasan yang berlawanan, kami juga dapat mengecualikan daftar tertaut yang diurutkan, karena mereka memerlukan pemindaian daftar setidaknya hingga elemen pertama yang lebih besar dari atau sama dengan kata atau awalan yang dicari.

Dua opsi yang valid menggunakan daftar yang didukung array yang diurutkan atau pohon biner.
Pada daftar yang didukung array yang diurutkan, kita dapat menggunakan pencarian biner untuk menemukan urutan saat ini jika ada atau elemen yang lebih besar berikutnya dengan biaya O(log2(n)) , di mana n adalah jumlah kata dalam kamus.

Kita dapat mengimplementasikan kosa kata yang didukung array yang selalu mempertahankan urutan seperti ini, menggunakan standar java.util.ArrayList dan java.util.Collections.binarySeach :

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

Jika kami memutuskan untuk menggunakan pohon biner, implementasinya bisa lebih pendek dan lebih elegan (sekali lagi, ini tautan ke kodenya):

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

Dalam kedua kasus, kita dapat mengharapkan kinerja O(log n) untuk setiap metode akses ( contains() dan isPrefix() ). Untuk kebutuhan ruang, baik implementasi yang didukung array maupun implementasi yang didukung pohon memerlukan O(n+M) di mana n adalah jumlah kata dalam kamus dan M adalah ukuran byte kamus, yaitu jumlah dari panjang string dalam kamus.

Aplikasi Trie: Kapan dan Mengapa Menggunakan Tries

Performa logaritmik dan memori linier tidak buruk. Namun ada beberapa karakteristik lagi dari domain aplikasi kami yang dapat membawa kami ke kinerja yang lebih baik:

• Kita dapat dengan aman berasumsi bahwa semua kata adalah huruf kecil.
• Kami hanya menerima huruf az—tanpa tanda baca, tanpa tanda hubung, tanpa aksen, dll.
• Kamus berisi banyak bentuk infleksi: jamak, kata kerja terkonjugasi, kata gabungan (misalnya, rumah –> pengurus rumah tangga). Oleh karena itu, banyak kata memiliki batang yang sama .
• Kata-kata memiliki panjang yang terbatas. Misalnya, jika kita sedang mengerjakan papan 4x4, semua kata yang lebih panjang dari 16 karakter dapat dibuang.

Di sinilah trie (diucapkan "try") masuk. Tapi apa sebenarnya trie itu? Mencoba adalah struktur data yang diabaikan, ditemukan di buku tetapi jarang di perpustakaan standar.

Untuk motivasi, pertama-tama mari kita pertimbangkan anak poster Ilmu Komputer: pohon biner. Sekarang, ketika kami menganalisis kinerja pohon biner dan mengatakan operasi x adalah O(log(n)) , kami terus-menerus berbicara basis log 2. Tetapi bagaimana jika, alih-alih pohon biner, kami menggunakan pohon ternary, di mana setiap node memiliki tiga anak (atau, fan-out dari tiga). Kemudian, kita akan berbicara log base 3. (Itu adalah peningkatan kinerja, meskipun hanya dengan faktor konstan.) Pada dasarnya, pohon kita akan menjadi lebih lebar tetapi lebih pendek, dan kita dapat melakukan lebih sedikit pencarian karena kita tidak perlu turun terlalu jauh. begitu dalam.

Mengambil langkah lebih jauh, bagaimana jika kita memiliki pohon dengan fan-out yang sama dengan jumlah nilai yang mungkin dari tipe data kita?

Inilah motivasi di balik trie. Dan seperti yang mungkin sudah Anda duga, trie memang pohon, bisa dibilang pohon trie!

Namun, berbeda dengan kebanyakan pohon biner yang akan Anda gunakan untuk menyortir string, yang akan menyimpan seluruh kata dalam simpulnya, setiap simpul dari trie memegang satu karakter (dan bahkan bukan itu, seperti yang akan kita lihat segera) dan memiliki fan-out maksimum yang sama dengan panjang alfabet. Dalam kasus kami, panjang alfabet adalah 26; oleh karena itu simpul dari trie memiliki fan-out maksimum 26. Dan, sementara pohon biner seimbang memiliki kedalaman log2(n) , kedalaman maksimum trie sama dengan panjang maksimum sebuah kata! (Sekali lagi, lebih lebar tetapi lebih pendek.)

Dalam trie, kata-kata dengan batang (awalan) yang sama berbagi area memori yang sesuai dengan batang tersebut.

Untuk memvisualisasikan perbedaannya, mari kita lihat kamus kecil yang terdiri dari lima kata. Asumsikan bahwa huruf Yunani menunjukkan pointer, dan perhatikan bahwa di trie, karakter merah menunjukkan node memegang kata-kata yang valid .

Implementasi Java Trie

Seperti yang kita ketahui, di pohon pointer ke elemen anak biasanya diimplementasikan dengan variabel kiri dan kanan, karena fan-out maksimum ditetapkan pada dua.

Dalam trie yang mengindeks alfabet 26 huruf, setiap simpul memiliki 26 kemungkinan anak dan, oleh karena itu, 26 kemungkinan penunjuk. Dengan demikian, setiap node menampilkan larik 26 (penunjuk ke) sub-pohon, di mana setiap nilai dapat berupa null (jika tidak ada anak seperti itu) atau node lain.

Lalu, bagaimana kita mencari kata dalam sebuah trie? Berikut adalah metode yang, diberi String s , akan mengidentifikasi simpul yang sesuai dengan huruf terakhir dari kata, jika ada di pohon:

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

Metode LOWERCASE.getIndex(s.charAt(i)) hanya mengembalikan posisi karakter ke- i dalam alfabet. Pada simpul yang dikembalikan, node properti Boolean menunjukkan bahwa simpul tersebut sesuai dengan huruf terakhir dari sebuah kata, yaitu huruf yang ditandai dengan warna merah pada contoh sebelumnya. Karena setiap simpul menyimpan penghitung jumlah anak, jika penghitung ini positif maka ada kata yang lebih panjang dalam kamus yang memiliki string saat ini sebagai awalan. Catatan: simpul tidak benar-benar perlu menyimpan referensi ke karakter yang terkait dengannya, karena itu tersirat dalam posisinya di trie.

Menganalisis Kinerja

Apa yang membuat struktur trie benar-benar berkinerja baik dalam situasi ini adalah bahwa biaya mencari kata atau awalan adalah tetap dan hanya bergantung pada jumlah karakter dalam kata dan bukan pada ukuran kosa kata.

Dalam domain khusus kami, karena kami memiliki string yang paling banyak 16 karakter, tepat 16 langkah diperlukan untuk menemukan kata yang ada dalam kosakata, sementara jawaban negatif apa pun, yaitu kata atau awalan yang tidak ada dalam trie, dapat diperoleh paling banyak 16 langkah juga! Mempertimbangkan bahwa kami sebelumnya telah mengabaikan panjang string saat menghitung kompleksitas waktu berjalan untuk daftar terurut yang didukung array dan pohon, yang disembunyikan dalam perbandingan string, kami juga dapat mengabaikannya di sini dan dengan aman menyatakan bahwa pencarian selesai dalam waktu O(1) .

Mempertimbangkan persyaratan ruang (dan mengingat bahwa kami telah menunjukkan dengan M ukuran byte kamus), trie dapat memiliki M node dalam kasus terburuk, jika tidak ada dua string yang berbagi awalan. Tetapi karena kami telah mengamati bahwa ada tingkat redundansi yang tinggi dalam kamus, ada banyak kompresi yang harus dilakukan. Kamus bahasa Inggris yang digunakan dalam kode contoh adalah 935.017 byte dan membutuhkan 250.264 node, dengan rasio kompresi sekitar 73%.

Namun, meskipun demikian, bahkan trie terkompresi biasanya akan membutuhkan lebih banyak memori daripada pohon atau larik. Ini karena, untuk setiap node, diperlukan setidaknya 26 x sizeof(pointer) byte, ditambah beberapa overhead untuk objek dan atribut tambahan. Pada mesin 64-bit, setiap node membutuhkan lebih dari 200 byte, sedangkan karakter string membutuhkan satu byte, atau dua jika kita mempertimbangkan string UTF.

Percobaan dan Tes Kinerja

Jadi, bagaimana dengan kinerja? Implementasi kosakata diuji dalam dua situasi berbeda: memeriksa 20.000.000 string acak dan menemukan semua kata dalam 15.000 papan yang dihasilkan secara acak dari daftar kata yang sama.

Empat struktur data dianalisis: daftar terurut yang didukung array, pohon biner, trie yang dijelaskan di atas, dan trie menggunakan array byte yang sesuai dengan indeks alfabet dari karakter itu sendiri (optimasi kinerja kecil dan mudah diimplementasikan). Berikut adalah hasilnya, dalam ms:

Jumlah rata-rata gerakan yang dilakukan untuk menyelesaikan papan adalah 2.188. Untuk setiap gerakan, pencarian kata dan pencarian awalan dilakukan, yaitu, untuk memeriksa semua papan, lebih dari 32 juta pencarian kata dan 32 juta pencarian awalan dilakukan. Catatan: ini bisa dilakukan dalam satu langkah, saya memisahkannya untuk kejelasan dalam eksposisi. Memadatkan mereka dalam satu langkah akan memotong waktu untuk memecahkan papan hampir setengahnya, dan mungkin akan lebih menyukai trie.

Seperti dapat dilihat di atas, pencarian kata tampil lebih baik dengan trie bahkan saat menggunakan string, dan bahkan lebih cepat saat menggunakan indeks alfabet, dengan yang terakhir berkinerja lebih dari dua kali lebih cepat dari pohon biner standar. Perbedaan dalam memecahkan papan bahkan lebih jelas, dengan solusi cepat trie-alphabet-index lebih dari empat kali lebih cepat dari daftar dan pohon.

Membungkus

Trie adalah struktur data yang sangat khusus yang membutuhkan lebih banyak memori daripada pohon dan daftar. Namun, ketika karakteristik domain tertentu berlaku, seperti alfabet terbatas dan redundansi tinggi di bagian pertama string, ini bisa sangat efektif dalam menangani pengoptimalan kinerja.

Referensi

Penjelasan ekstensif tentang try dan alfabet dapat ditemukan di bab 5 buku Robert Sedgewick "Algorithms, 4th edition". Situs web pendamping di Princeton memiliki kode untuk implementasi Alphabet dan TrieST yang lebih luas daripada contoh saya.

Deskripsi trie dan implementasi untuk berbagai bahasa juga dapat ditemukan di Wikipedia dan Anda juga dapat melihat sumber daya trie Universitas Boston ini.