Apakah ada algoritma pencarian yang bagus untuk satu karakter?

Saya tahu beberapa algoritma pencocokan string dasar seperti KMP atau Boyer-Moore, tetapi semua itu menganalisis pola sebelum mencari. Namun, jika seseorang memiliki karakter tunggal, tidak banyak yang bisa dianalisis. Jadi apakah ada algoritma yang lebih baik daripada pencarian naif membandingkan setiap karakter teks?

Dipahami bahwa kasus terburuknya adalah O(N), ada beberapa optimasi mikro yang sangat bagus.

Metode naif melakukan perbandingan karakter dan perbandingan akhir teks untuk setiap karakter.

Menggunakan sentinel (yaitu salinan karakter target di akhir teks) mengurangi jumlah perbandingan hingga 1 per karakter.

Pada level twiddling ada:

#define haszero(v)      ( ((v) - 0x01010101UL) & ~(v) & 0x80808080UL )
#define hasvalue(x, n)  ( haszero((x) ^ (~0UL / 255 * (n))) )

untuk mengetahui apakah byte dalam kata ( x) memiliki nilai tertentu ( n).

Subekspresi v - 0x01010101UL, dievaluasi menjadi bit tinggi yang diatur dalam byte mana pun setiap kali byte yang sesuai dalam vadalah nol atau lebih besar dari 0x80.

Sub-ekspresi ~v & 0x80808080ULmengevaluasi bit tinggi yang diatur dalam byte di mana byte vtidak memiliki bit set yang tinggi (sehingga byte kurang dari 0x80).

Dengan ANDing dua sub-ekspresi ini ( haszero) hasilnya adalah bit tinggi yang ditetapkan di mana byte dalam vnol, karena bit tinggi yang ditetapkan karena nilai yang lebih besar daripada 0x80dalam sub-ekspresi pertama ditutup oleh yang kedua (27 April, 1987 oleh Alan Mycroft).

Sekarang kita dapat XOR nilai untuk diuji ( x) dengan kata yang telah diisi dengan nilai byte yang kita minati ( n). Karena XORing nilai dengan itu sendiri menghasilkan byte nol dan bukan nol sebaliknya, kita dapat meneruskan hasilnya haszero.

Ini sering digunakan dalam strchrimplementasi yang khas .

(Stephen M Bennet menyarankan ini pada 13 Desember 2009. Rincian lebih lanjut dalam Bit Twiddling Hacks yang terkenal ).

PS

kode ini rusak untuk kombinasi apa pun 1111di sebelah a0

Retasan melewati tes brute force (bersabarlah):

#include <iostream>
#include <limits>

bool haszero(std::uint32_t v)
{
  return (v - std::uint32_t(0x01010101)) & ~v & std::uint32_t(0x80808080);
}

bool hasvalue(std::uint32_t x, unsigned char n)
{
  return haszero(x ^ (~std::uint32_t(0) / 255 * n));
}

bool hasvalue_slow(std::uint32_t x, unsigned char n)
{
  for (unsigned i(0); i < 32; i += 8)
    if (((x >> i) & 0xFF) == n)
      return true;

  return false;
}

int main()
{
  const std::uint64_t stop(std::numeric_limits<std::uint32_t>::max());

  for (unsigned c(0); c < 256; ++c)
  {
    std::cout << "Testing " << c << std::endl;

    for (std::uint64_t w(0); w != stop; ++w)
    {
      if (w && w % 100000000 == 0)
        std::cout << w * 100 / stop << "%\r" << std::flush;

      const bool h(hasvalue(w, c));
      const bool hs(hasvalue_slow(w, c));

      if (h != hs)
        std::cerr << "hasvalue(" << w << ',' << c << ") is " << h << '\n';
    }
  }

  return 0;
}

Banyak upvotes untuk jawaban yang membuat asumsi satu karakter = satu byte, yang saat ini bukan standar lagi

Terima kasih atas komentarnya.

Jawabannya dimaksudkan untuk apa pun kecuali esai tentang pengkodean multi-byte / variabel-lebar :-) (dalam semua keadilan itu bukan bidang keahlian saya dan saya tidak yakin itu yang dicari OP).

Pokoknya menurut saya ide / trik di atas agak bisa disesuaikan dengan MBE (terutama penyandian sinkronisasi sendiri ):

• seperti dicatat dalam komentar Johan, hack dapat 'dengan mudah' diperluas untuk bekerja dengan byte ganda atau apa pun (tentu saja Anda tidak dapat merentangkannya terlalu banyak);
• fungsi khas yang menempatkan karakter dalam string karakter multibyte:
  • berisi panggilan ke strchr/ strstr(mis. GNUlib coreutils mbschr )
  • mengharapkan mereka disetel dengan baik.
• teknik sentinel dapat digunakan dengan sedikit tinjauan ke depan.

Algoritme pencarian teks apa pun yang mencari setiap kemunculan satu karakter dalam teks yang diberikan harus membaca setiap karakter teks setidaknya satu kali, itu harus jelas. Dan karena ini cukup untuk pencarian satu kali, tidak ada algoritma yang lebih baik (ketika berpikir dalam hal run time order, yang disebut "linear" atau O (N) untuk kasus ini, di mana N adalah jumlah karakter untuk mencari melalui).

Namun, untuk implementasi nyata, pasti ada banyak optimasi mikro yang dimungkinkan, yang tidak mengubah urutan waktu proses secara keseluruhan, tetapi menurunkan waktu proses yang sebenarnya. Dan jika tujuannya bukan untuk menemukan setiap kemunculan satu karakter, tetapi hanya yang pertama, Anda bisa berhenti pada kemunculan pertama, tentu saja. Namun demikian, bahkan untuk kasus itu, yang terburuk masih karakter yang Anda cari adalah karakter terakhir dalam teks, jadi urutan waktu terburuk untuk tujuan ini masih O (N).

Jika "tumpukan jerami" Anda dicari lebih dari sekali, pendekatan berbasis histogram akan menjadi sangat cepat. Setelah histogram dibuat, Anda hanya perlu pencarian pointer untuk menemukan jawaban Anda.

Jika Anda hanya perlu tahu apakah pola yang dicari ada, penghitung sederhana dapat membantu. Dapat diperluas untuk memasukkan posisi di mana setiap karakter ditemukan di tumpukan jerami, atau posisi kejadian pertama.

string haystack = "agtuhvrth";
array<int, 256> histogram{0};
for(character: haystack)
     ++histogram[character];

if(histogram['a'])
    // a belongs to haystack

Jika Anda perlu mencari karakter di string yang sama ini lebih dari sekali, maka pendekatan yang mungkin adalah membagi string menjadi bagian-bagian yang lebih kecil, mungkin secara rekursif, dan menggunakan filter bloom untuk masing-masing bagian ini.

Karena filter bloom dapat memberi tahu Anda dengan pasti jika suatu karakter tidak berada di bagian string yang "diwakili" oleh filter, Anda dapat melewati beberapa bagian saat mencari karakter.

Sebagai contoh: Untuk string berikut, seseorang dapat membaginya menjadi 4 bagian (masing-masing sepanjang 11 karakter), dan mengisi setiap bagian dengan filter bloom (mungkin 4 byte besar) dengan karakter bagian itu:

The quick brown fox jumps over the lazy dog 
          |          |          |          |

Anda dapat mempercepat pencarian Anda, misalnya untuk karakter a: Menggunakan fungsi hash yang baik untuk filter bloom, mereka akan memberi tahu Anda bahwa - dengan probabilitas tinggi - Anda tidak perlu mencari di bagian pertama, kedua atau ketiga. Dengan demikian Anda menyelamatkan diri dari memeriksa 33 karakter dan alih-alih hanya perlu memeriksa 16 byte (untuk 4 filter mekar). Ini masih O(n), hanya dengan faktor konstan (fraksional) (dan agar ini menjadi efektif, Anda harus memilih bagian yang lebih besar, untuk meminimalkan overhead menghitung fungsi hash untuk karakter pencarian).

Menggunakan pendekatan rekursif, seperti pohon akan membuat Anda dekat O(log n):

The quick brown fox jumps over the lazy dog 
   |   |   |   |   |   |   |   |---|-X-|   |  (1 Byte)
       |       |       |       |---X---|----  (2 Byte)
               |               |-----X------  (3 Byte)
-------------------------------|-----X------  (4 Byte)
---------------------X---------------------|  (5 Byte)

Dalam konfigurasi ini kita perlu (sekali lagi, dengan asumsi kita beruntung dan tidak mendapatkan false positive dari salah satu filter) untuk memeriksanya

5 + 2*4 + 3 + 2*2 + 2*1 bytes

untuk sampai ke bagian akhir (di mana orang perlu memeriksa 3 karakter sampai menemukan a).

Dengan menggunakan skema subdivisi yang baik (lebih baik seperti di atas) Anda harus mendapatkan hasil yang cukup bagus dengan itu. (Catatan: Filter Bloom pada akar pohon harus lebih besar daripada dekat dengan daun, seperti yang ditunjukkan dalam contoh, untuk mendapatkan probabilitas positif palsu yang rendah)

Jika string akan dicari berkali-kali (masalah "pencarian" khas), solusinya bisa O (1). Solusi adalah membangun indeks.

Misalnya:

Peta, di mana Kunci adalah Karakter dan Nilai adalah daftar indeks untuk karakter tersebut dalam string.

Dengan ini, pencarian peta tunggal dapat memberikan jawabannya.