¿Hay algún buen algoritmo de búsqueda para un solo personaje?

Conozco varios algoritmos básicos de coincidencia de cadenas como KMP o Boyer-Moore, pero todos analizan el patrón antes de buscar. Sin embargo, si uno tiene un solo carácter, no hay mucho para analizar. Entonces, ¿hay algún algoritmo mejor que la ingenua búsqueda de comparar cada carácter del texto?

Se entiende que el peor de los casos es que O(N)hay algunas micro optimizaciones muy buenas.

El método ingenuo realiza una comparación de caracteres y una comparación de final de texto para cada carácter.

El uso de un centinela (es decir, una copia del carácter objetivo al final del texto) reduce el número de comparaciones a 1 por carácter.

En el nivel de twiddling hay:

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

para saber si algún byte en una palabra ( x) tiene un valor específico ( n).

La subexpresión se v - 0x01010101ULevalúa como un conjunto de bits alto en cualquier byte siempre que el byte correspondiente vsea ​​cero o mayor que 0x80.

La subexpresión se ~v & 0x80808080ULevalúa en bits altos establecidos en bytes donde el byte de vno tiene su conjunto de bits alto (por lo que el byte era menor que 0x80).

Al ANDing estas dos subexpresiones ( haszero), el resultado es el conjunto de bits altos donde los bytes en veran cero, ya que los bits altos establecidos debido a un valor mayor que 0x80en la primera subexpresión se enmascaran en la segunda (27 de abril, 1987 por Alan Mycroft).

Ahora podemos XOR el valor para probar ( x) con una palabra que se ha llenado con el valor de byte en el que estamos interesados ​​( n). Debido a que XORing un valor consigo mismo da como resultado un byte cero y distinto de cero, podemos pasar el resultado a haszero.

Esto se usa a menudo en una strchrimplementación típica .

(Stephen M Bennet sugirió esto el 13 de diciembre de 2009. Más detalles en los conocidos Bit Twiddling Hacks ).

PD

este código está roto para cualquier combinación de 1111's al lado de un0

El truco pasa la prueba de fuerza bruta (solo sea paciente):

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

Muchos votos a favor por una respuesta que hace que la suposición sea un carácter = un byte, que hoy en día ya no es el estándar

Gracias por el comentario

La respuesta debía ser cualquier cosa menos un ensayo sobre codificaciones de varios bytes / ancho variable :-) (para ser justos, esa no es mi área de especialización y no estoy seguro de que sea lo que estaba buscando el OP).

De todos modos, me parece que las ideas / trucos anteriores podrían adaptarse de alguna manera al MBE (especialmente las codificaciones de sincronización automática ):

• como se señaló en el comentario de Johan, el hack puede "fácilmente" extenderse para trabajar por bytes dobles o cualquier otra cosa (por supuesto, no se puede estirar demasiado);
• Una función típica que localiza un carácter en una cadena de caracteres multibyte:
  • contiene llamadas a strchr/ strstr(por ejemplo, GNUlib coreutils mbschr )
  • espera que estén bien sintonizados.
• La técnica centinela se puede utilizar con un poco de previsión.

Cualquier algoritmo de búsqueda de texto que busque cada aparición de un solo carácter en un texto dado tiene que leer cada carácter del texto al menos una vez, eso debería ser obvio. Y dado que esto es suficiente para una búsqueda única, no puede haber un algoritmo mejor (cuando se piensa en términos de orden de tiempo de ejecución, que se llama "lineal" u O (N) para este caso, donde N es el número de caracteres para buscar a través de).

Sin embargo, para implementaciones reales, seguramente hay muchas microoptimizaciones posibles, que no cambian el orden del tiempo de ejecución en general, sino que reducen el tiempo de ejecución real. Y si el objetivo no es encontrar cada aparición de un solo personaje, sino solo la primera, puede detenerse en la primera aparición, por supuesto. Sin embargo, incluso para ese caso, el peor de los casos es que el personaje que está buscando es el último personaje del texto, por lo que el orden de tiempo de ejecución del peor caso para este objetivo sigue siendo O (N).

Si se busca su "pajar" más de una vez, un enfoque basado en histograma será extremadamente rápido. Después de construir el histograma, solo necesita una búsqueda de puntero para encontrar su respuesta.

Si solo necesita saber si el patrón buscado está presente, un simple contador puede ayudar. Se puede extender para incluir las posiciones en las que se encuentra cada personaje en el pajar, o la posición de la primera ocurrencia.

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

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

Si necesita buscar caracteres en esta misma cadena más de una vez, entonces un posible enfoque es dividir la cadena en partes más pequeñas, posiblemente de manera recursiva, y usar filtros de floración para cada una de estas partes.

Dado que un filtro de floración puede decirle con seguridad si un carácter no está en la parte de la cadena que está "representada" por el filtro, puede omitir algunas partes mientras busca caracteres.

Como ejemplo: para la siguiente cadena, se podría dividir en 4 partes (cada una de 11 caracteres de longitud) y llenar para cada parte un filtro de floración (quizás de 4 bytes) con los caracteres de esa parte:

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

Puede acelerar su búsqueda, por ejemplo, para el personaje a: utilizando buenas funciones hash para los filtros de floración, le dirán que, con alta probabilidad, no tiene que buscar ni en la primera, segunda ni tercera parte. Por lo tanto, se ahorra la comprobación de 33 caracteres y, en cambio, solo tiene que comprobar 16 bytes (para los 4 filtros de floración). Esto sigue siendo O(n), solo con un factor constante (fraccionario) (y para que esto sea efectivo, deberá elegir partes más grandes, para minimizar la sobrecarga de calcular las funciones hash para el carácter de búsqueda).

El uso de un enfoque recursivo en forma de árbol debería acercarte 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)

En esta configuración, uno necesita (nuevamente, suponiendo que tuvimos suerte y no obtuvimos un falso positivo de uno de los filtros) para verificar

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

para llegar a la parte final (donde hay que verificar 3 caracteres hasta encontrar el a).

Usando un buen esquema de subdivisión (mejor que el anterior), debería obtener resultados bastante buenos con eso. (Nota: los filtros Bloom en la raíz del árbol deben ser más grandes que cerca de las hojas, como se muestra en el ejemplo, para obtener una baja probabilidad de falsos positivos)

Si la cadena se va a buscar varias veces (problema típico de "búsqueda"), la solución puede ser O (1). La solución es construir un índice.

P.ej :

Mapa, donde la clave es el carácter y el valor es una lista de índices para ese carácter en la cadena.

Con esto, una sola búsqueda en el mapa puede proporcionar la respuesta.