Есть ли хороший алгоритм поиска для одного символа?

Я знаю несколько основных алгоритмов сопоставления строк, таких как KMP или Boyer-Moore, но все они анализируют паттерн перед поиском. Однако, если один из них содержит один символ, анализировать особо нечего. Так есть ли лучший алгоритм, чем наивный поиск, сравнивающий каждый символ текста?

Понятно, что в худшем случае O(N)есть несколько очень хороших микрооптимизаций.

Наивный метод выполняет сравнение символов и сравнение конца текста для каждого символа.

Использование часового (то есть копия целевого символа в конце текста) уменьшает количество сравнений до 1 на символ.

На уровне немного

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

знать, имеет ли какой-либо байт в слове ( x) конкретное значение ( n).

Подвыражение v - 0x01010101ULоценивается как старший бит, установленный в любом байте, когда соответствующий байт в vноль или больше, чем 0x80.

Подвыражение ~v & 0x80808080ULоценивается старшими битами, установленными в байтах, где байт vне имеет своего старшего установленного бита (таким образом, байт был меньше чем 0x80).

Посредством AND этих двух подвыражений ( haszero) результатом является набор старших бит, где байты в vбыли равны нулю, поскольку старшие биты, установленные из-за значения, большего, чем 0x80в первом подвыражении, маскируются вторым (27 апреля, 1987 Алан Майкрофт).

Теперь мы можем XOR значение для test ( x) со словом, которое было заполнено байтовым значением, в котором мы заинтересованы ( n). Поскольку XOR значения с самим собой приводит к нулевому байту и ненулевой в противном случае, мы можем передать результат haszero.

Это часто используется в типичной strchrреализации.

(Стивен Беннет предложил это 13 декабря 2009 года. Дальнейшие подробности можно найти в хорошо известных « хихикающих битах» ).

PS

этот код не работает для любой комбинации 1111рядом с0

Хак проходит тест грубой силы (просто наберитесь терпения):

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

Много голосов за ответ, который делает предположение, что один символ = один байт, что в настоящее время уже не стандарт

Спасибо за замечание.

Ответ должен был быть чем угодно, но не эссе о многобайтовой / переменной ширине кодировки :-) (честно говоря, это не моя область знаний, и я не уверен, что это то, что ищет ОП).

В любом случае, мне кажется, что вышеприведенные идеи / приемы могут быть в некоторой степени адаптированы к MBE (особенно самосинхронизирующиеся кодировки ):

• как отмечено в комментарии Йохана, хак «легко» может быть расширен для работы с двойными байтами или чем-то еще (конечно, вы не можете растянуть его слишком сильно);
• типичная функция, которая находит символ в многобайтовой символьной строке:
  • содержит вызовы strchr/ strstr(например, GNUlib coreutils mbschr )
  • ожидает, что они будут хорошо настроены.
• сторожевую технику можно использовать с небольшим предвидением.

Любой алгоритм текстового поиска, который ищет каждый символ отдельного символа в данном тексте, должен прочитать каждый символ текста хотя бы один раз, что должно быть очевидно. И поскольку этого достаточно для одноразового поиска, лучшего алгоритма не может быть (если рассматривать в терминах порядка времени выполнения, который в данном случае называется «линейным» или O (N), где N - количество символов) искать через).

Тем не менее, для реальных реализаций, безусловно, возможно много микрооптимизаций, которые не изменяют порядок времени выполнения в целом, но снижают фактическое время выполнения. И если цель состоит не в том, чтобы найти каждый случай отдельного персонажа, а только первого, вы, конечно, можете остановиться в первом случае. Тем не менее, даже для этого случая, наихудший случай все еще состоит в том, что искомый символ является последним символом в тексте, поэтому наихудший порядок времени выполнения для этой цели по-прежнему равен O (N).

Если ваш «стог сена» ищется более одного раза, гистограммный подход будет очень быстрым. После построения гистограммы вам нужен только поиск по указателю, чтобы найти ваш ответ.

Если вам нужно только знать, присутствует ли искомый шаблон, может помочь простой счетчик. Его можно расширить, чтобы включить позицию (позиции), в которой каждый персонаж находится в стоге сена, или позицию первого вхождения.

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

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

Если вам нужно искать символы в одной и той же строке более одного раза, то возможный подход - разделить строку на более мелкие части, возможно, рекурсивно, и использовать фильтры Блума для каждой из этих частей.

Так как цветение фильтр может с уверенностью сказать , если персонаж не в той части строки , которая « в лицо» с помощью фильтра, вы можете пропустить некоторые части при поиске символов.

Например: для следующей строки можно разбить ее на 4 части (каждая длиной 11 символов) и заполнить для каждой части фильтр Блума (возможно, размером 4 байта) с символами этой части:

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

Вы можете ускорить поиск, например, для персонажа a: используя хорошие хэш-функции для фильтров Блума, они скажут вам, что - с большой вероятностью - вам не нужно искать ни в первой, ни во второй, ни в третьей части. Таким образом вы избавляете себя от проверки 33 символов и вместо этого должны проверять только 16 байтов (для 4 фильтров Блума). Это все еще O(n), только с постоянным (дробным) фактором (и для того, чтобы это было эффективным, вам нужно будет выбирать большие части, чтобы минимизировать накладные расходы на вычисление хеш-функций для символа поиска).

Использование рекурсивного, древовидного подхода должно привести вас к следующему 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)

В этой конфигурации нужно (опять-таки, предположим, что нам повезло и мы не получили ложного срабатывания от одного из фильтров), чтобы проверить

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

чтобы добраться до финальной части (где нужно проверить 3 символа, пока не найдется a).

Используя хорошую (лучше, как указано выше) схему подразделений, вы должны получить довольно хорошие результаты с этим. (Примечание: фильтры Блума в корне дерева должны быть больше, чем близко к листьям, как показано в примере, чтобы получить низкую вероятность ложных срабатываний)

Если в строке будет производиться поиск несколько раз (типичная проблема «поиска»), решение может быть O (1). Решение заключается в создании индекса.

Например:

Карта, где Key - это символ, а Value - список индексов для этого символа в строке.

С этим, единственный поиск карты может обеспечить ответ.