Czy istnieje jakiś dobry algorytm wyszukiwania dla pojedynczego znaku?

Znam kilka podstawowych algorytmów dopasowywania ciągów, takich jak KMP lub Boyer-Moore, ale wszystkie z nich analizują wzorzec przed wyszukiwaniem, jednak jeśli jeden znak jest pojedynczy, nie ma wiele do przeanalizowania. Czy istnieje więc lepszy algorytm niż naiwne wyszukiwanie polegające na porównywaniu każdego znaku tekstu?

Przyjmuje się, że najgorszym przypadkiem jest O(N)kilka bardzo dobrych mikrooptymalizacji.

Naiwna metoda przeprowadza porównanie znaków i porównanie końca tekstu dla każdego znaku.

Użycie wartownika (tj. Kopii znaku docelowego na końcu tekstu) zmniejsza liczbę porównań do 1 na znak.

Na nieco kręcącym się poziomie jest:

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

wiedzieć, czy dowolny bajt w słowie ( x) ma określoną wartość ( n).

Podwyrażenie v - 0x01010101UL, ocenia na wysoki bit ustawiony w dowolnym bajcie, ilekroć odpowiedni bajt vjest równy zero lub większy niż 0x80.

Podwyrażenie ~v & 0x80808080ULocenia na wysokie bity ustawione w bajtach, w których bajt vnie ma ustawionego wysokiego bitu (więc bajt był mniejszy niż 0x80).

Dzięki ANDingowi tych dwóch podwyrażeń ( haszero) wynikiem jest zestaw wysokich bitów, w którym bajty vbyły zerowe, ponieważ zestaw wysokich bitów z powodu wartości większej niż 0x80w pierwszym podwyrażeniu jest maskowany przez drugi (27 kwietnia, 1987 Alan Mycroft).

Teraz możemy XOR wartość testować ( x) słowem wypełnionym wartością bajtu, która nas interesuje ( n). Ponieważ XORing samej wartości powoduje zerowy bajt, w przeciwnym razie niezerowy, możemy przekazać wynik do haszero.

Jest to często używane w typowej strchrimplementacji.

(Stephen M. Bennet zasugerował to 13 grudnia 2009 r. Dalsze szczegóły w dobrze znanym Bit Twiddling Hacks ).

PS

ten kod jest uszkodzony dla dowolnej kombinacji 1111znaków obok0

Hack przechodzi test brutalnej siły (bądź cierpliwy):

#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;
}

Dużo głosów poparcia dla odpowiedzi, która sprawia, że ​​założenie to jeden znak = jeden bajt, co obecnie nie jest już standardem

Dziękuję za uwagę.

Odpowiedź miała być tylko esejem na temat kodowania wielobajtowego / o zmiennej szerokości :-) (szczerze mówiąc, to nie jest moja specjalizacja i nie jestem pewien, czy tego szukał PO).

W każdym razie wydaje mi się, że powyższe pomysły / sztuczki można nieco dostosować do MBE (szczególnie kodowania samosynchronizującego ):

• jak zauważono w komentarzu Johana, hack można „łatwo” rozszerzyć na podwójne bajty lub cokolwiek innego (oczywiście nie można tego zbytnio rozciągnąć);
• typowa funkcja, która lokalizuje znak w ciągu znaków wielobajtowych:
  • zawiera wywołania do strchr/ strstr(np. GNUlib coreutils mbschr )
  • oczekuje, że będą dobrze dostrojone.
• technika wartownika może być użyta z odrobiną dalekowzroczności.

Każdy algorytm wyszukiwania tekstu, który wyszukuje każde wystąpienie pojedynczego znaku w danym tekście, musi odczytać każdy znak tekstu przynajmniej raz, co powinno być oczywiste. A ponieważ jest to wystarczające do jednorazowego wyszukiwania, nie może być lepszego algorytmu (przy myśleniu w kategoriach kolejności w czasie wykonywania, która w tym przypadku nazywa się „liniowa” lub O (N), gdzie N jest liczbą znaków przeszukiwać).

Jednak w przypadku rzeczywistych wdrożeń z pewnością istnieje wiele mikrooptymalizacji, które nie zmieniają w ogóle kolejności wykonywania, ale obniżają rzeczywisty czas wykonywania. A jeśli celem nie jest znalezienie każdego wystąpienia jednej postaci, ale tylko pierwszego, możesz oczywiście zatrzymać się przy pierwszym wystąpieniu. Niemniej jednak, nawet w tym przypadku, najgorszym przypadkiem jest nadal to, że postać, której szukasz, jest ostatnią postacią w tekście, więc kolejność najgorszego przypadku dla tego celu nadal wynosi O (N).

Jeśli Twój „stóg siana” zostanie przeszukany więcej niż raz, podejście oparte na histogramie będzie niezwykle szybkie. Po zbudowaniu histogramu wystarczy wyszukać wskaźnik, aby znaleźć odpowiedź.

Jeśli potrzebujesz tylko wiedzieć, czy szukany wzór jest obecny, prosty licznik może pomóc. Można go rozszerzyć o pozycję (pozycje), w których każda postać znajduje się w stogu siana, lub pozycję pierwszego wystąpienia.

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

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

Jeśli musisz szukać znaków w tym samym łańcuchu więcej niż raz, możliwe jest podzielenie łańcucha na mniejsze części, możliwie rekurencyjnie, i użycie filtrów Bloom dla każdej z tych części.

Ponieważ filtr rozkwitu może z całą pewnością stwierdzić, czy znak nie znajduje się w części ciągu „reprezentowanej” przez filtr, możesz pominąć niektóre części podczas wyszukiwania znaków.

Jako przykład: dla następującego ciągu można podzielić go na 4 części (każdy o długości 11 znaków) i wypełnić dla każdej części filtr Bloom (być może 4 bajty) znakami tej części:

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

Możesz przyspieszyć wyszukiwanie, np. Dla postaci a: Używając dobrych funkcji skrótu dla filtrów kwitnienia, powiedzą ci, że - z dużym prawdopodobieństwem - nie musisz szukać ani w pierwszej, ani w drugiej, ani w trzeciej części. W ten sposób oszczędzasz się przed sprawdzaniem 33 znaków i zamiast tego musisz tylko sprawdzić 16 bajtów (dla 4 filtrów Blooma). Jest to nadal O(n), tylko ze stałym (ułamkowym) współczynnikiem (aby to zadziałało, musisz wybrać większe części, aby zminimalizować koszty obliczeń funkcji skrótu dla szukanego znaku).

Korzystanie z rekurencyjnego, drzewiastego podejścia powinno zbliżyć cię do 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)

W tej konfiguracji należy (ponownie, zakładając, że mieliśmy szczęście i nie otrzymaliśmy fałszywego wyniku pozytywnego z jednego z filtrów) do sprawdzenia

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

dostać się do ostatniej części (gdzie trzeba sprawdzić 3 znaki, aż do znalezienia a).

Stosując dobry (lepszy jak wyżej) schemat podziału, powinieneś uzyskać z tym całkiem niezłe wyniki. (Uwaga: filtry Bloom u nasady drzewa powinny być większe niż blisko liści, jak pokazano w przykładzie, aby uzyskać niskie prawdopodobieństwo fałszywie dodatnich wyników)

Jeśli ciąg ma być przeszukiwany wiele razy (typowy problem „wyszukiwania”), rozwiązaniem może być O (1). Rozwiązaniem jest zbudowanie indeksu.

Np .:

Mapa, gdzie klucz jest znakiem, a wartość jest listą indeksów tego znaku w ciągu.

Dzięki temu jedno wyszukiwanie mapy może dać odpowiedź.