Struktur data atau algoritma untuk menemukan perbedaan antar string dengan cepat

Saya memiliki array 100.000 string, semuanya panjang $k$ . Saya ingin membandingkan setiap string dengan setiap string lain untuk melihat apakah ada dua string berbeda dengan 1 karakter. Saat ini, ketika saya menambahkan setiap string ke array, saya memeriksa setiap string yang sudah ada dalam array, yang memiliki kompleksitas waktu dari .$\frac{n(n-1)}{2} k$

Apakah ada struktur data atau algoritma yang dapat membandingkan string satu sama lain lebih cepat daripada yang sudah saya lakukan?

Beberapa informasi tambahan:

• Urutan penting: abcdedan xbcdeberbeda menurut 1 karakter, sementara abcdedanedcba berbeda dengan 4 karakter.

• Untuk setiap pasangan string yang berbeda oleh satu karakter, saya akan menghapus salah satu string dari array.

• Saat ini, saya mencari string yang berbeda hanya dengan 1 karakter, tapi alangkah baiknya jika perbedaan 1 karakter itu dapat ditingkatkan menjadi, katakanlah, 2, 3, atau 4 karakter. Namun, dalam hal ini, saya pikir efisiensi lebih penting daripada kemampuan untuk meningkatkan batas perbedaan karakter.

• $k$ biasanya dalam kisaran 20-40.

Ini mungkin untuk mencapai kasus terburuk berjalan waktu.$O(nk \log k)$

Mari kita mulai dari yang sederhana. Jika Anda peduli dengan solusi yang mudah diimplementasikan yang akan efisien pada banyak input, tetapi tidak semua, di sini adalah solusi yang sederhana, pragmatis, mudah diterapkan yang cukup banyak dalam praktik untuk banyak situasi. Itu jatuh kembali ke waktu berjalan kuadrat dalam kasus terburuk, meskipun.

Ambil setiap string dan simpan dalam hashtable, dengan kunci pada bagian pertama dari string. Kemudian, ulangi ember hashtable. Untuk setiap pasangan string dalam ember yang sama, periksa apakah mereka berbeda dalam 1 karakter (yaitu, periksa apakah paruh keduanya berbeda dalam 1 karakter).

Kemudian, ambil setiap string dan simpan dalam hashtable, kali ini dikunci pada bagian kedua dari string. Sekali lagi periksa setiap pasangan string dalam ember yang sama.

Dengan asumsi string baik-didistribusikan, waktu berjalan kemungkinan akan sekitar . Selain itu, jika ada sepasang string yang berbeda dengan 1 karakter, itu akan ditemukan selama salah satu dari dua lintasan (karena mereka berbeda dengan hanya 1 karakter, bahwa karakter yang berbeda harus berada di bagian pertama atau kedua dari string, jadi bagian kedua atau pertama dari string harus sama). Namun, dalam kasus terburuk (mis., Jika semua string dimulai atau diakhiri dengan karakter k / 2 yang sama ), ini menurunkan ke waktu berjalan O ( n 2 k ) , sehingga waktu berjalan terburuknya bukan peningkatan pada brute force .$O(nk)$$k/2$$O(n^2 k)$

Sebagai pengoptimalan kinerja, jika ada bucket yang memiliki terlalu banyak string, Anda dapat mengulangi proses yang sama secara rekursif untuk mencari pasangan yang berbeda satu karakter. Doa rekursif akan menggunakan string dengan panjang $k/2$ .

Jika Anda peduli dengan waktu pengoperasian terburuk:

Dengan optimalisasi kinerja di atas saya percaya terburuk berjalan waktu .$O(nk \log k)$

Solusi saya mirip dengan j_random_hacker tetapi hanya menggunakan satu set hash.

Saya akan membuat satu set string hash. Untuk setiap string dalam input, tambahkan ke set $k$ string. Di setiap string, ganti salah satu huruf dengan karakter khusus, tidak ditemukan dalam string. Saat Anda menambahkannya, periksa apakah belum ada di set. Jika ya, maka Anda memiliki dua string yang hanya berbeda dengan (paling banyak) satu karakter.

Contoh dengan string 'abc', 'adc'

Untuk abc kita tambahkan '* bc', 'a * c' dan 'ab *'

Untuk adc kita tambahkan '* dc', 'a * c' dan 'iklan *'

Ketika kita menambahkan 'a * c' yang kedua kali kita perhatikan itu sudah di set, jadi kita tahu bahwa ada dua string yang hanya berbeda dengan satu huruf.

Total waktu berjalan dari algoritma ini adalah . Ini karena kita membuat k string baru untuk semua n string dalam input. Untuk setiap string tersebut, kita perlu menghitung hash, yang biasanya membutuhkan waktu O ( k ) .$O(n*k^2)$$k$$n$$O(k)$

Menyimpan semua string membutuhkan ruang .$O(n*k^2)$

Perbaikan lebih lanjut

Kita dapat meningkatkan algoritme lebih lanjut dengan tidak menyimpan string yang dimodifikasi secara langsung tetapi sebaliknya menyimpan objek dengan referensi ke string asli dan indeks karakter yang bertopeng. Dengan cara ini kita tidak perlu membuat semua string dan kita hanya perlu ruang untuk menyimpan semua objek.$O(n*k)$

Anda perlu menerapkan fungsi hash khusus untuk objek. Kita dapat mengambil implementasi Java sebagai contoh, lihat dokumentasi java . Java hashCode mengalikan nilai unicode setiap karakter dengan (dengan k panjang string dan i indeks berbasis satu karakter. Perhatikan bahwa setiap string yang diubah hanya berbeda oleh satu karakter dari aslinya. Kita dapat dengan mudah menghitung kontribusi karakter itu ke kode hash. Kita dapat mengurangi itu dan menambahkan karakter masking kita sebagai gantinya. Ini membutuhkan O ( 1 ) untuk menghitung. Ini memungkinkan kita untuk membawa total waktu berjalan ke O ( $31^{k-i}$$k$$i$$O(1)$$O(n*k)$

Saya akan membuat hashtables H 1 , ... , H k , yang masing-masing memiliki ( k - 1 ) string yang -Panjang sebagai kunci dan daftar nomor (ID string) sebagai nilai. Hashtable H i akan berisi semua string yang diproses sejauh ini tetapi dengan karakter pada posisi saya hapus . Misalnya, jika k = 6 , maka H 3 [ A B D E F ] akan berisi daftar semua string yang terlihat sejauh ini yang memiliki pola $k$$H_1, \dots, H_k$$(k-1)$$H_i$$i$$k=6$$H_3[ABDEF]$ , di mana ⋅ berarti "karakter apa saja". Kemudian untuk memproses j -th input string s j :$AB\cdot DEF$$\cdot$$j$$s_j$

1. Untuk setiap dalam kisaran 1 hingga k : $i$$k$
   • Bentuk string dengan menghapus karakter ke- i dari s j .$s_j'$$i$$s_j$
   • Carilah . Setiap ID string di sini mengidentifikasi string asli yang sama dengan s , atau berbeda pada posisi i saja. Keluarkan ini sebagai kecocokan untuk string s j . (Jika Anda ingin mengecualikan duplikat yang tepat, buat tipe nilai dari hashtable menjadi (string ID, karakter yang dihapus), sehingga Anda dapat menguji mereka yang memiliki karakter yang sama dihapus seperti yang baru saja kami hapus dari s j .)$H_i[s_j']$$s$$i$$s_j$$s_j$
   • Masukkan ke H i untuk permintaan di masa mendatang.$j$$H_i$

Jika kita menyimpan setiap tombol hash secara eksplisit, maka kita harus menggunakan ruang dan dengan demikian memiliki kompleksitas waktu setidaknya itu. Tetapi seperti yang dijelaskan oleh Simon Prins , adalah mungkin untuk merepresentasikan serangkaian modifikasi pada string (dalam kasusnya digambarkan sebagai mengubah karakter tunggal menjadi , di tambang sebagai penghapusan) secara implisit sedemikian rupa sehingga semua kunci hash k untuk string tertentu hanya perlu Ruang O ( k ) , mengarah ke ruang O ( n k ) secara keseluruhan, dan membuka kemungkinan O ( n k $O(nk^2)$*$k$$O(k)$$O(nk)$$O(nk)$waktu juga. Untuk mencapai kompleksitas waktu ini, kita memerlukan cara untuk menghitung hash untuk semua variasi string panjang- k dalam waktu O ( k ) : misalnya, ini dapat dilakukan dengan menggunakan hash polinomial, seperti yang disarankan oleh DW (dan ini adalah kemungkinan jauh lebih baik daripada hanya XOR karakter yang dihapus dengan hash untuk string asli).$k$$k$$O(k)$

Trik representasi implisit Simon Prins juga berarti bahwa "penghapusan" masing-masing karakter tidak benar-benar dilakukan, sehingga kita dapat menggunakan representasi berbasis array yang biasa dari string tanpa penalti kinerja (bukan daftar terkait seperti yang saya sarankan pada awalnya).

Berikut adalah pendekatan hashtable yang lebih kuat daripada metode polinomial-hash. Pertama menghasilkan bilangan bulat positif acak r 1 .. k yang coprime dengan hashtable ukuran M . Yaitu, 0 ≤ r i < M . Kemudian hash setiap string x 1 .. k ke ( Σ k i = 1 x i r i ) mod M . Ada hampir tidak ada musuh yang bisa dilakukan untuk menyebabkan tabrakan sangat tidak merata, karena Anda menghasilkan r 1 .. k pada run-time dan sehingga $k$$r_{1..k}$$M$$0 \le r_i < M$$x_{1..k}$$(\sum_{i=1}^k x_i r_i ) \bmod M$$r_{1..k}$$k$meningkatkan kemungkinan maksimum tabrakan dari setiap pasangan diberikan string yang berbeda berjalan cepat ke . Juga jelas bagaimana menghitung dalam waktu O ( k ) semua hash yang mungkin untuk setiap string dengan satu karakter berubah.$1/M$$O(k)$

Jika Anda benar-benar ingin menjamin hashing yang seragam, Anda dapat menghasilkan satu bilangan asli acak kurang dari M untuk setiap pasangan ( i , c ) untuk i dari 1 hingga k dan untuk setiap karakter c , lalu hash setiap string x 1 .. k to ( ∑ k i = 1 r ( i , x i ) ) mod $r(i,c)$$M$$(i,c)$$i$$1$$k$$c$$x_{1..k}$$(\sum_{i=1}^k r(i,x_i) ) \bmod M$. Maka probabilitas tabrakan dari setiap pasangan diberikan string yang berbeda adalah persis . Pendekatan ini lebih baik jika rangkaian karakter Anda relatif kecil dibandingkan dengan n .$1/M$$n$

Banyak algoritma yang diposting di sini menggunakan sedikit ruang pada tabel hash. Berikut ini adalah algoritma sederhana runtime penyimpanan tambahan O ( ( n lg n ) ⋅ k 2 ) .$O(1)$$O((n \lg n) \cdot k^2)$

Caranya adalah dengan menggunakan , yang merupakan pembanding antara dua nilai a dan b yang mengembalikan true jika a < b (leksikografis) sambil mengabaikan karakter k th. Maka algoritma adalah sebagai berikut.$C_k(a, b)$$a$$b$$a < b$$k$

Pertama, cukup urutkan string secara teratur dan lakukan pemindaian linier untuk menghapus duplikat apa pun.

Kemudian, untuk setiap :$k$

1. Menyortir string dengan sebagai pembanding.$C_k$

2. String yang hanya berbeda dalam sekarang berdekatan dan dapat dideteksi dalam pemindaian linier.$k$

Dua string panjang k , berbeda dalam satu karakter, berbagi awalan panjang l dan akhiran panjang m sedemikian sehingga k = l + m + 1 .

Jawaban oleh Simon Prins mengkodekan ini dengan menyimpan semua kombinasi awalan / akhiran secara eksplisit, yaitu abcmenjadi *bc, a*cdan ab*. Itu k = 3, l = 0,1,2 dan m = 2,1,0.

Seperti yang ditunjukkan valarMorghulis, Anda dapat mengatur kata-kata di pohon awalan. Ada juga pohon sufiks yang sangat mirip. Cukup mudah untuk menambah pohon dengan jumlah simpul daun di bawah setiap awalan atau akhiran; ini dapat diperbarui dalam O (k) saat memasukkan kata baru.

Alasan Anda menginginkan jumlah saudara ini adalah agar Anda tahu, diberi kata baru, apakah Anda ingin menghitung semua string dengan awalan yang sama atau apakah untuk menghitung semua string dengan akhiran yang sama. Misalnya untuk "abc" sebagai input, awalan yang mungkin adalah "", "a" dan "ab", sedangkan sufiks yang sesuai adalah "bc", "c" dan "". Seperti sudah jelas, untuk sufiks pendek, lebih baik untuk menyebutkan saudara kandung di pohon awalan dan sebaliknya.

Seperti yang ditunjukkan oleh @einpoklum, tentu saja semua string memiliki awalan k / 2 yang sama . Itu bukan masalah untuk pendekatan ini; pohon awalan akan linier hingga kedalaman k / 2 dengan setiap node hingga kedalaman k / 2 adalah nenek moyang 100.000 simpul daun. Akibatnya, pohon sufiks akan digunakan hingga kedalaman (k / 2-1), yang baik karena string harus berbeda dalam sufiksnya mengingat mereka berbagi awalan.

[sunting] Sebagai pengoptimalan, setelah Anda menentukan awalan unik terpendek dari sebuah string, Anda tahu bahwa jika ada satu karakter yang berbeda, itu harus menjadi karakter terakhir dari awalan, dan Anda akan menemukan duplikat terdekat saat memeriksa awalan yang lebih pendek. Jadi jika "abcde" memiliki awalan unik terpendek "abc", itu berarti ada string lain yang dimulai dengan "ab?" tetapi tidak dengan "abc". Jika mereka berbeda hanya dalam satu karakter, itu adalah karakter ketiga. Anda tidak perlu memeriksa "abc? E" lagi.

Dengan logika yang sama, jika Anda akan menemukan bahwa "cde" adalah sufiks terpendek yang unik, maka Anda tahu bahwa Anda perlu memeriksa hanya awalan panjang-2 "ab" dan bukan awalan panjang 1 atau 3.

Perhatikan bahwa metode ini hanya bekerja untuk satu perbedaan karakter dan tidak menggeneralisasi ke 2 perbedaan karakter, itu bergantung pada satu karakter sebagai pemisahan antara awalan yang identik dan akhiran yang identik.

Menyimpan string dalam ember adalah cara yang baik (sudah ada jawaban yang berbeda menguraikan ini).

Solusi alternatif bisa dengan menyimpan string dalam daftar yang disortir . Caranya adalah dengan mengurutkan berdasarkan algoritma hashing yang sensitif terhadap lokalitas . Ini adalah algoritma hash yang menghasilkan hasil yang sama ketika inputnya serupa [1].

Setiap kali Anda ingin menyelidiki string, Anda bisa menghitung hash dan lookup posisi hash yang dalam daftar diurutkan Anda (mengambil untuk array atau O ( n ) untuk daftar link). Jika Anda menemukan bahwa tetangga (mempertimbangkan semua tetangga dekat, tidak hanya mereka yang memiliki indeks +/- 1) dari posisi itu serupa (tidak aktif oleh satu karakter), Anda menemukan pasangan Anda. Jika tidak ada string serupa, Anda dapat memasukkan string baru pada posisi yang Anda temukan (yang mengambil O ( 1 ) untuk daftar tertaut dan O ( n ) untuk array).$O(log(n))$$O(n)$$O(1)$$O(n)$

Salah satu kemungkinan algoritma hashing yang sensitif terhadap lokalitas adalah Nilsimsa (dengan implementasi open source yang tersedia misalnya dengan python ).

[1]: Perhatikan bahwa algoritma hash yang sering, seperti SHA1, dirancang untuk sebaliknya: menghasilkan hash yang sangat berbeda untuk input yang serupa, tetapi tidak sama.

Penafian: Sejujurnya, saya secara pribadi akan mengimplementasikan salah satu solusi bucket bersarang / diatur pohon untuk aplikasi produksi. Namun, ide daftar yang diurutkan menurut saya sebagai alternatif yang menarik. Perhatikan bahwa algoritma ini sangat tergantung pada algoritma hash yang dipilih. Nilsimsa adalah salah satu algoritma yang saya temukan - ada lebih banyak lagi meskipun (misalnya TLSH, Ssdeep dan Sdhash). Saya belum memverifikasi bahwa Nilsimsa bekerja dengan algoritme yang diuraikan di atas.

Seseorang dapat mencapai solusi dalam waktu dan O $O(nk+ n^2)$ menggunakan array suffix yang ditingkatkan(arraySuffixbersama denganarray LCP) yang memungkinkan kueri LCP (Longest Common Prefix) waktu yang konstan (yaitu Diberikan dua indeks string, berapa panjang awalan terpanjang dari sufiks yang dimulai dari indeks tersebut). Di sini, kita dapat mengambil keuntungan dari kenyataan bahwa semua string memiliki panjang yang sama. Secara khusus,$O(nk)$

1. Buat susunan akhiran yang disempurnakan dari semua string yang digabungkan bersama. Misalkan X = x 1 . x 2 . x 3 . . . . x n di mana x i , ∀ $n$$X = x_1.x_2.x_3 .... x_n$ adalah string dalam koleksi. Membangun array akhiran dan LCP array untuk X .$x_i, \forall 1 \le i \le n$$X$

2. Sekarang setiap mulai pada posisi ( i - 1 ) k dalam pengindeksan berbasis nol. Untuk setiap string x i , ambil LCP dengan masing-masing string x j sedemikian rupa sehingga j < i . Jika LCP melampaui akhir x j maka x i = x j . Kalau tidak, ada ketidakcocokan (katakanlah x i [ p ] ≠ x j [ p $x_i$$(i-1)k$$x_i$$x_j$$j<i$$x_j$$x_i = x_j$$x_i[p] \ne x_j[p]$); dalam hal ini ambil LCP lain mulai dari posisi yang sesuai setelah ketidakcocokan. Jika LCP kedua melampaui akhir maka x i dan x j berbeda hanya dengan satu karakter; jika tidak, ada lebih dari satu ketidakcocokan.$x_j$$x_i$$x_j$

   for (i=2; i<= n; ++i){
       i_pos = (i-1)k;
       for (j=1; j < i; ++j){
           j_pos = (j-1)k;
           lcp_len = LCP (i_pos, j_pos);
           if (lcp_len < k) { // mismatch
               if (lcp_len == k-1) { // mismatch at the last position
               // Output the pair (i, j)
               }
               else {
                 second_lcp_len = LCP (i_pos+lcp_len+1, j_pos+lcp_len+1);
                 if (lcp_len+second_lcp_len>=k-1) { // second lcp goes beyond
                   // Output the pair(i, j)
                 }
               }
           }
       }
   }
   

Anda bisa menggunakan perpustakaan SDSL untuk membangun array suffix dalam bentuk terkompresi dan menjawab pertanyaan LCP.

Analisis: Membangun berbagai akhiran ditingkatkan adalah linear dalam panjang yaitu O ( n k ) . Setiap permintaan LCP membutuhkan waktu yang konstan. Dengan demikian, waktu query adalah O ( n 2 ) .$X$$O(nk)$$O(n^2)$

Generalisasi: Pendekatan ini juga dapat digeneralisasi ke lebih dari satu ketidakcocokan. Secara umum, waktu berjalan adalah mana q adalah jumlah ketidakcocokan yang diizinkan.$O(nk + qn^2)$$q$

Jika Anda ingin menghapus string dari koleksi, alih-alih memeriksa setiap , Anda bisa menyimpan daftar hanya 'valid' j .$j<i$$j$

Satu perbaikan untuk semua solusi yang diusulkan. Mereka semua membutuhkan memori dalam kasus terburuk. Anda dapat menguranginya dengan menghitung hash string dengan bukan masing-masing karakter, yaitu , ... dan memproses di setiap pass hanya varian dengan nilai hash dalam rentang integer tertentu. Fe dengan nilai hash genap di lintasan pertama, dan nilai hash ganjil di yang kedua.$O(nk)$**bcdea*cde

Anda juga dapat menggunakan pendekatan ini untuk membagi pekerjaan di antara beberapa inti CPU / GPU.

Ini adalah versi singkat dari jawaban @SimonPrins yang tidak melibatkan hash.

Dengan asumsi tidak ada string Anda yang mengandung tanda bintang:

1. Buat daftar ukuran $nk$ di mana masing-masing string Anda terjadi di $k$ variasi, masing-masing memiliki satu huruf digantikan oleh tanda bintang (runtime $\mathcal{O}(nk^2)$)
2. Sortir daftar itu (runtime $\mathcal{O}(nk^2\log nk)$)
3. Periksa duplikat dengan membandingkan entri berikutnya dari daftar yang diurutkan (runtime $\mathcal{O}(nk^2)$)

Solusi alternatif dengan penggunaan hash dalam Python (tidak dapat menahan keindahan):

def has_almost_repeats(strings,k):
    variations = [s[:i-1]+'*'+s[i+1:] for s in strings for i in range(k)]
    return len(set(variations))==k*len(strings)

Inilah pendapat saya tentang 2+ finder mismatch. Perhatikan bahwa dalam posting ini saya menganggap setiap string sebagai lingkaran, dengan substring panjang 2 pada indeks k-1terdiri dari simbol str[k-1]diikuti oleh str[0]. Dan substring dengan panjang 2 pada indeks -1adalah sama!

Jika kami memiliki Mketidaksesuaian antara dua string panjang k, mereka memiliki substring yang cocok dengan panjang setidaknya$mlen(k,M) = \lceil{k/M}\rceil-1$karena, dalam kasus terburuk, simbol yang tidak cocok membagi string (melingkar) menjadi Msegmen berukuran sama. Fe dengan k=20dan M=4kecocokan "terburuk" mungkin memiliki polanya abcd*efgh*ijkl*mnop*.

Sekarang, algoritma untuk mencari semua ketidakcocokan hingga Msimbol di antara string ksimbol:

• untuk setiap i dari 0 hingga k-1
  • pisahkan semua string menjadi grup dengan str[i..i+L-1], di mana L = mlen(k,M). Jika L=4dan jika Anda memiliki alfabet hanya 4 simbol (dari DNA), ini akan membuat 256 kelompok.
  • Grup yang lebih kecil dari ~ 100 string dapat diperiksa dengan algoritma brute-force
  • Untuk kelompok yang lebih besar, kita harus melakukan pembagian sekunder:
    • Hapus dari setiap string dalam Lsimbol grup yang sudah kami cocokkan
    • untuk setiap j dari i-L +1 ke kL-1
      • pisahkan semua string menjadi grup dengan str[i..i+L1-1], di mana L1 = mlen(k-L,M). Jika k=20, M=4, alphabet of 4 symbols, begitu L=4dan L1=3, ini akan membuat 64 kelompok.
      • sisanya dibiarkan sebagai latihan untuk pembaca: D

Kenapa kita tidak mulai jdari 0? Karena kami telah membuat grup-grup ini dengan nilai yang sama i, maka pekerjaan dengan j<=i-Lakan persis sama dengan pekerjaan dengan nilai i dan j yang ditukar.

Optimasi lebih lanjut:

• Di setiap posisi, pertimbangkan juga string str[i..i+L-2] & str[i+L]. Ini hanya menggandakan jumlah pekerjaan yang dibuat, tetapi memungkinkan untuk meningkat Lsebesar 1 (jika matematika saya benar). Jadi, daripada 256 grup, Anda akan membagi data menjadi 1024 grup.
• Jika beberapa $L[i]$menjadi terlalu kecil, kita selalu dapat menggunakan *triknya: untuk setiap i in in 0..k-1, hapus simbol ke-i dari setiap string dan buat pekerjaan mencari M-1ketidakcocokan dalam string panjang tersebut k-1.

Saya bekerja setiap hari untuk menemukan dan mengoptimalkan algo, jadi jika Anda membutuhkan setiap bit kinerja terakhir, itulah rencananya:

• Periksa dengan *masing-masing posisi secara independen, yaitu alih-alih n*kvarian string pemroses pekerjaan tunggal - mulai kpekerjaan independen masing-masing nstring pengecekan . Anda dapat menyebarkan kpekerjaan ini di antara beberapa inti CPU / GPU. Ini sangat penting jika Anda akan memeriksa 2+ char diffs. Ukuran pekerjaan yang lebih kecil juga akan meningkatkan lokalitas cache, yang dengan sendirinya dapat membuat program 10x lebih cepat.
• Jika Anda akan menggunakan tabel hash, gunakan implementasi Anda sendiri menggunakan linear probing dan ~ 50% load factor. Ini cepat dan sangat mudah diimplementasikan. Atau gunakan implementasi yang ada dengan pengalamatan terbuka. Tabel hash STL lambat karena penggunaan rantai terpisah.
• Anda dapat mencoba untuk memfilter data menggunakan filter Bloom 3-negara (membedakan kejadian 0/1/1 +) seperti yang diusulkan oleh @AlexReynolds.
• Untuk setiap i dari 0 hingga k-1 jalankan pekerjaan berikut:
  • Hasilkan struct 8-byte yang berisi 4-5 byte hash dari setiap string (dengan *posisi ke-i) dan indeks string, dan kemudian urutkan atau bangun tabel hash dari catatan ini.

Untuk menyortir, Anda dapat mencoba kombo berikut:

• pass pertama adalah MSD radix sort dalam 64-256 cara menggunakan trik TLB
• pass kedua adalah MSD radix sort dalam 256-1024 cara tanpa trik TLB (total 64K cara)
• pass ketiga adalah jenis penyisipan untuk memperbaiki ketidakkonsistenan yang tersisa