Memutuskan apakah string wildcard benar-benar cocok dengan string wildcard dalam satu set

Inilah masalah yang telah mengganggu saya untuk sementara waktu. Katakanlah string adalah urutan 1s dan 0s, dan string wildcard adalah urutan 1, 0, dan? S. Semua string dan string wildcard memiliki panjang yang sama. Ini adalah wildcard UNIX standar; 10 ?? 1 cocok 10011, 10111, dll - a? cocok dengan 1 atau 0 di posisi itu. Jika dan w adalah string wildcard, maka kami menulis jika setiap string yang cocok dengan juga cocok dengan .$v$$w$v $v \leq w$$v$$w$

Masalahnya : diberi satu set string wildcard, dan kueri (juga string wildcard), apakah ada sehingga ? Dan jika tidak, dapatkah kita menambahkan ke efisien?v w ∈ S v ≤ w v $S$$v$$w \in S$$v \leq w$$v$$S$

Inilah solusi (di mana adalah ukuran string, adalah ukuran kata RAM (biasanya 32 atau 64)): lihat setiap elemen daftar dan uji kondisi (yang dapat dilakukan dalam 2 atau 3 operasi menggunakan bit-twiddling). Juga uji apakah berlaku untuk setiap item saat kami memindai. Jika gagal dalam pengujian kami, maka tambahkan ke set, dan hapus kami tandai.kmv≥wwvv$O(\frac{k}{m}n)$$k$$m$$v \geq w$$w$$v$$v$$w$

Tapi itu tidak cukup cepat. Akan sangat keren jika ada solusi , atau, di dunia yang sempurna, kompleksitas mirip dengan pohon radix ( ). Ini juga OK untuk kueri yang kira-kira benar : yaitu, jika , maka kembalikan ya atau tidak; tetapi jika kondisinya tidak tahan pasti mengembalikan no.O ( k ) v ≤ $O(\log n)$$O(k)$$v \leq w$

Meskipun ini tidak membantu kompleksitas kasus terburuk, Anda dapat mengasumsikan bahwa semua elemen di dibatasi oleh string wildcard; yaitu, ada beberapa sedemikian rupa sehingga untuk semua , .v w ∈ S v ≥ $S$$v$$w \in S$$v \geq w$

Gagasan yang sudah saya coba

• String wildcard membentuk join-semilattice. Kita bisa memiliki pohon n-ary yang memegang string wildcard; dedaunan akan menjadi string wildcard, dan cabang-cabangnya akan mewakili gabungan dari semua anak. Jika kueri dan gabungan tidak dapat dibandingkan, maka kita tidak perlu membuang waktu untuk mencoba membandingkan dengan semua anak dari cabang itu. Lebih jauh, jika kita membuat pembaruan, dan pembaruan itu terjadi lebih besar dari gabungan, kita bisa menghapus seluruh cabang. Sayangnya, ini masih dalam kasus terburuk, dan kami tidak selalu menemukan gabungan "terbaik" yang dibuat saat memindai melalui pohon untuk menambahkan elemen.$O(n)$
• Satu bisa membentuk trie radix dari . Kita tahu bahwa dibatasi oleh beberapa string wildcard; anggap itu? 0? 0. Maka semua cabang dari trie hanya harus berada pada bit 1 dan 3 dari string. Jika bit saat ini kami bercabang pada query adalah 1, kita harus memeriksa? dan 1 cabang; jika 0, kita periksa? dan 0 cabang; jika ya ?, kami hanya memeriksa? cabang. Karena kita harus berpotensi mengambil banyak cabang, ini sepertinya tidak terlalu bagus (sulit untuk memperbarui trie karena alasan yang sama). Karena pencocokan adalah operasi yang sangat cepat, sakit dibandingkan dengan strategi naif untuk melakukan banyak melintasi pohon (mengikuti banyak petunjuk jauh lebih mahal daripada melakukan beberapa OR dan AND).$S$$S$

Pekerjaan yang berhubungan

• Di komunitas jejaring, masalah ini bermanifestasi sebagai "klasifikasi paket", berikut ini adalah survei yang bagus tentang algoritma dan struktur data yang dikenal . Sayangnya, asumsi hampir selalu dibuat bahwa string wildcard hanya cocok dengan awalan, dan kueri adalah tuple dari string tersebut. Tentu saja, kita selalu dapat mengonversi string wildcard umum untuk memenuhi kriteria ini: 1? 00? 1 ?? adalah (1,?, 0, 0,?, 1,?,?). Ini tidak akan efisien. Asumsi lain yang dibuat adalah bahwa tupel ini dikaitkan dengan "warna", dan kueri harus mengembalikan warna (bukan hanya itu yang cocok). Ini membuat masalahnya jauh lebih sulit, karena kita harus memesan tupel (atau kalau tidak, ambigu mana dari (0,?) Dan (?, 1) yang cocok (0, 1)).

• Di komunitas algoritme, saya telah menemukan banyak hasil yang terkait dengan menemukan substring yang cocok dengan "tidak peduli". Ini adalah masalah yang jauh lebih sulit, dan saya tidak bisa memanfaatkan salah satu tekniknya.

Kesimpulannya

Terima kasih atas bantuannya!

$S$$O(k)$

$S$

Sedangkan untuk menambahkan string ke mesin, ada beberapa pekerjaan baru-baru ini tentang mengubah otomat kondisi-terbatas secara bertahap. Lihat makalah ini oleh Daciuk et al: "Konstruksi Tambahan dari Minimal Acyclic Finite-State Automata".

Apakah ini membantu?