strupr - ¿La forma más rápida de hacer una búsqueda de subcadenas insensible a mayúsculas y minúsculas en C/C++?

strlwr c++

Question

Nota

La pregunta a continuación se hizo en 2008 sobre algún código de 2003. Como muestra la actualización del OP, esta publicación completa ha quedado obsoleta por los algoritmos de la cosecha 2008 y solo persiste aquí como curiosidad histórica.

Necesito hacer una búsqueda rápida de subcadenas insensible a mayúsculas y minúsculas en C / C ++. Mis requisitos son los siguientes:

• Debería comportarse como strstr () (es decir, devolver un puntero al punto de coincidencia).
• Debe ser insensible a mayúsculas y minúsculas (doh).
• Debe soportar la configuración regional actual.
• Debe estar disponible en Windows (MSVC ++ 8.0) o ser fácilmente portable a Windows (es decir, desde una biblioteca de código abierto).

Aquí está la implementación actual que estoy usando (tomada de la Biblioteca GNU C):

/* Return the offset of one string within another.
Copyright (C) 1994,1996,1997,1998,1999,2000 Free Software Foundation, Inc.
This file is part of the GNU C Library.
The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
The GNU C Library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with the GNU C Library; if not, write to the Free
Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
02111-1307 USA. */
/*
* My personal strstr() implementation that beats most other algorithms.
* Until someone tells me otherwise, I assume that this is the
* fastest implementation of strstr() in C.
* I deliberately chose not to comment it. You should have at least
* as much fun trying to understand it, as I had to write it :-).
*
* Stephen R. van den Berg, [email protected] */
/*
* Modified to use table lookup instead of tolower(), since tolower() isn''t
* worth s*** on Windows.
*
* -- Anders Sandvig ([email protected])
*/
#if HAVE_CONFIG_H
# include <config.h>
#endif
#include <ctype.h>
#include <string.h>
typedef unsigned chartype;
char char_table[256];
void init_stristr(void)
{
int i;
char string[2];
string[1] = ''/0'';
for (i = 0; i < 256; i++)
{
string[0] = i;
_strlwr(string);
char_table[i] = string[0];
}
}
#define my_tolower(a) ((chartype) char_table[a])
char *
my_stristr (phaystack, pneedle)
const char *phaystack;
const char *pneedle;
{
register const unsigned char *haystack, *needle;
register chartype b, c;
haystack = (const unsigned char *) phaystack;
needle = (const unsigned char *) pneedle;
b = my_tolower (*needle);
if (b != ''/0'')
{
haystack--; /* possible ANSI violation */
do
{
c = *++haystack;
if (c == ''/0'')
goto ret0;
}
while (my_tolower (c) != (int) b);
c = my_tolower (*++needle);
if (c == ''/0'')
goto foundneedle;
++needle;
goto jin;
for (;;)
{
register chartype a;
register const unsigned char *rhaystack, *rneedle;
do
{
a = *++haystack;
if (a == ''/0'')
goto ret0;
if (my_tolower (a) == (int) b)
break;
a = *++haystack;
if (a == ''/0'')
goto ret0;
shloop:
;
}
while (my_tolower (a) != (int) b);
jin:
a = *++haystack;
if (a == ''/0'')
goto ret0;
if (my_tolower (a) != (int) c)
goto shloop;
rhaystack = haystack-- + 1;
rneedle = needle;
a = my_tolower (*rneedle);
if (my_tolower (*rhaystack) == (int) a)
do
{
if (a == ''/0'')
goto foundneedle;
++rhaystack;
a = my_tolower (*++needle);
if (my_tolower (*rhaystack) != (int) a)
break;
if (a == ''/0'')
goto foundneedle;
++rhaystack;
a = my_tolower (*++needle);
}
while (my_tolower (*rhaystack) == (int) a);
needle = rneedle; /* took the register-poor approach */
if (a == ''/0'')
break;
}
}
foundneedle:
return (char*) haystack;
ret0:
return 0;
}

¿Puedes hacer que este código sea más rápido o conoces una mejor implementación?

Nota: Noté que la Biblioteca GNU C ahora tiene una nueva implementación de strstr() , pero no estoy seguro de cuán fácilmente se puede modificar para que no distinga entre mayúsculas y minúsculas, o si es más rápido que el anterior (en mi caso). También noté que la implementación anterior aún se usa para cadenas de caracteres anchas , por lo que si alguien sabe por qué, por favor compártelo.

Actualizar

Para aclarar las cosas, en caso de que aún no lo haya hecho, no escribí esta función, es parte de la Biblioteca GNU C. Solo lo modifiqué para que no distinga entre mayúsculas y minúsculas.

Además, gracias por el consejo sobre strcasestr() y la comprobación de otras implementaciones de otras fuentes (como OpenBSD, FreeBSD, etc.). Parece ser el camino a seguir. El código anterior es de 2003, por lo que lo publiqué aquí con la esperanza de que esté disponible una versión mejor, que aparentemente es. :)

Answer 1

¿Por qué usas _strlwr (cadena)? en init_stristr ()? No es una función estándar. Presumiblemente es para soporte regional, pero como no es estándar, solo usaría:

char_table[i] = tolower(i);

Answer 2

Te aconsejo que tomes parte de la implementación de strcasestr común que ya existe. Por ejemplo, de glib, glibc, OpenBSD, FreeBSD, etc. Puede buscar más con google.com/codesearch. A continuación, puede realizar algunas mediciones de rendimiento y comparar las diferentes implementaciones.

Answer 3

Si desea eliminar los ciclos de la CPU, puede considerar esto: supongamos que estamos tratando con ASCII y no con Unicode.

Haz una tabla estática con 256 entradas. Cada entrada en la tabla es de 256 bits.

Para probar si dos caracteres son iguales, haz algo como esto:

if (BitLookup(table[char1], char2)) { /* match */ }

Para construir la tabla, estableces un bit en todas partes en la tabla [char1] donde consideras que coincide con char2. Entonces, al construir la tabla, debes establecer los bits en el índice para "a" y "A" en la entrada "a" (y la entrada "A").

Ahora esto se ralentizará para realizar la búsqueda de bits (la búsqueda de bits será un cambio, máscara y agregar lo más probable), por lo que podría usar en su lugar una tabla de bytes para que utilice 8 bits para representar 1 bit. Esto tomará 32K, así que ¡has llegado a un compromiso de tiempo / espacio! Es posible que deseemos hacer que la tabla sea más flexible, así que digamos que hacemos esto en su lugar; en su lugar, la tabla definirá congruencias.

Dos caracteres se consideran congruentes si y solo si hay una función que los define como equivalentes. Entonces ''A'' y ''a'' son congruentes para la insensibilidad de mayúsculas y minúsculas. ''A'', ''À'', ''Á'' y '''' son congruentes para la insensibilidad diacrítica.

Así que defines bitfields que corresponden a tus congruencias

#define kCongruentCase (1 << 0)
#define kCongruentDiacritical (1 << 1)
#define kCongruentVowel (1 << 2)
#define kCongruentConsonant (1 << 3)

Entonces tu prueba es algo como esto:

inline bool CharsAreCongruent(char c1, char c2, unsigned char congruency)
{
return (_congruencyTable[c1][c2] & congruency) != 0;
}
#define CaseInsensitiveCharEqual(c1, c2) CharsAreCongruent(c1, c2, kCongruentCase)

Este tipo de toqueteo de tablas descomunales es el corazón de ctype, por cierto.

Answer 4

Suponiendo que ambas cadenas de entrada ya están en minúscula.

int StringInStringFindFirst(const char* p_cText, const char* p_cSearchText)
{
int iTextSize = strlen(p_cText);
int iSearchTextSize = strlen(p_cSearchText);
char* p_cFound = NULL;
if(iTextSize >= iSearchTextSize)
{
int iCounter = 0;
while((iCounter + iSearchTextSize) <= iTextSize)
{
if(memcmp( (p_cText + iCounter), p_cSearchText, iSearchTextSize) == 0)
return iCounter;
iCounter ++;
}
}
return -1;
}

También podría intentar usar máscaras ... si, por ejemplo, la mayoría de las cadenas que va a comparar solo contienen caracteres de la aa la z, tal vez valga la pena hacer algo como esto.

long GetStringMask(const char* p_cText)
{
long lMask=0;
while(*p_cText != ''/0'')
{
if (*p_cText>=''a'' && *p_cText<=''z'')
lMask = lMask | (1 << (*p_cText - ''a'') );
else if(*p_cText != '' '')
{
lMask = 0;
break;
}
p_cText ++;
}
return lMask;
}

Entonces...

int main(int argc, char* argv[])
{
char* p_cText = "this is a test";
char* p_cSearchText = "test";
long lTextMask = GetStringMask(p_cText);
long lSearchMask = GetStringMask(p_cSearchText);
int iFoundAt = -1;
// If Both masks are Valid
if(lTextMask != 0 && lSearchMask != 0)
{
if((lTextMask & lSearchMask) == lSearchMask)
{
iFoundAt = StringInStringFindFirst(p_cText, p_cSearchText);
}
}
else
{
iFoundAt = StringInStringFindFirst(p_cText, p_cSearchText);
}
return 0;
}

Answer 5

use algo de cadena de refuerzo . Está disponible, multiplataforma y solo un archivo de encabezado (no hay biblioteca para vincular). Sin mencionar que deberías usar boost de todos modos.

#include <boost/algorithm/string/find.hpp>
const char* istrstr( const char* haystack, const char* needle )
{
using namespace boost;
iterator_range<char*> result = ifind_first( haystack, needle );
if( result ) return result.begin();
return NULL;
}

Answer 6

Si puede controlar la cadena de aguja para que siempre esté en minúscula, puede escribir una versión modificada de stristr () para evitar las búsquedas de eso, y así acelerar el código. No es tan general, pero puede ser más rápido, un poco más rápido. Se aplican comentarios similares al pajar, pero es más probable que lea el pajar de fuentes fuera de su control, ya que no puede estar seguro de que los datos cumplan con los requisitos.

Si la ganancia en el rendimiento vale la pena es otra pregunta por completo. Para el 99% de las aplicaciones, la respuesta es "No, no vale la pena". Su aplicación podría ser una de la minoría más pequeña donde sea importante. Más probablemente, no lo es.

Answer 7

Esto no tendrá en cuenta la configuración regional, pero si puede cambiar IS_ALPHA y TO_UPPER puede hacerlo para considerarlo.

#define IS_ALPHA(c) (((c) >= ''A'' && (c) <= ''Z'') || ((c) >= ''a'' && (c) <= ''z''))
#define TO_UPPER(c) ((c) & 0xDF)
char * __cdecl strstri (const char * str1, const char * str2){
char *cp = (char *) str1;
char *s1, *s2;
if ( !*str2 )
return((char *)str1);
while (*cp){
s1 = cp;
s2 = (char *) str2;
while ( *s1 && *s2 && (IS_ALPHA(*s1) && IS_ALPHA(*s2))?!(TO_UPPER(*s1) - TO_UPPER(*s2)):!(*s1-*s2))
++s1, ++s2;
if (!*s2)
return(cp);
++cp;
}
return(NULL);
}

Answer 8

Puede usar la función StrStrI que encuentra la primera aparición de una subcadena dentro de una cadena. La comparación no distingue entre mayúsculas y minúsculas. No olvides incluir su encabezado: Shlwapi.h. Mira esto: http://msdn.microsoft.com/en-us/library/windows/desktop/bb773439(v=vs.85).aspx

Answer 9

El código que publicaste es aproximadamente la mitad de rápido que strcasestr .

$ gcc -Wall -o my_stristr my_stristr.c
steve@solaris:~/code/tmp
$ gcc -Wall -o strcasestr strcasestr.c
steve@solaris:~/code/tmp
$ ./bench ./my_stristr > my_stristr.result ; ./bench ./strcasestr > strcasestr.result;
steve@solaris:~/code/tmp
$ cat my_stristr.result
run 1... time = 6.32
run 2... time = 6.31
run 3... time = 6.31
run 4... time = 6.31
run 5... time = 6.32
run 6... time = 6.31
run 7... time = 6.31
run 8... time = 6.31
run 9... time = 6.31
run 10... time = 6.31
average user time over 10 runs = 6.3120
steve@solaris:~/code/tmp
$ cat strcasestr.result
run 1... time = 3.82
run 2... time = 3.82
run 3... time = 3.82
run 4... time = 3.82
run 5... time = 3.82
run 6... time = 3.82
run 7... time = 3.82
run 8... time = 3.82
run 9... time = 3.82
run 10... time = 3.82
average user time over 10 runs = 3.8200
steve@solaris:~/code/tmp

La función main fue:

int main(void)
{
char * needle="hello";
char haystack[1024];
int i;
for(i=0;i<sizeof(haystack)-strlen(needle)-1;++i)
{
haystack[i]=''A''+i%57;
}
memcpy(haystack+i,needle, strlen(needle)+1);
/*printf("%s/n%d/n", haystack, haystack[strlen(haystack)]);*/
init_stristr();
for (i=0;i<1000000;++i)
{
/*my_stristr(haystack, needle);*/
strcasestr(haystack,needle);
}
return 0;
}

Fue modificado adecuadamente para probar ambas implementaciones. init_stristr que mientras escribía esto, lo dejé en la llamada init_stristr , pero no debería cambiar demasiado las cosas. bench es solo un simple script de shell:

#!/bin/bash
function bc_calc()
{
echo $(echo "scale=4;$1" | bc)
}
time="/usr/bin/time -p"
prog="$1"
accum=0
runs=10
for a in $(jot $runs 1 $runs)
do
echo -n "run $a... "
t=$($time $prog 2>&1| grep user | awk ''{print $2}'')
echo "time = $t"
accum=$(bc_calc "$accum+$t")
done
echo -n "average user time over $runs runs = "
echo $(bc_calc "$accum/$runs")

Answer 10

Para uso independiente de la plataforma:

const wchar_t *szk_wcsstri(const wchar_t *s1, const wchar_t *s2)
{
if (s1 == NULL || s2 == NULL) return NULL;
const wchar_t *cpws1 = s1, *cpws1_, *cpws2;
char ch1, ch2;
bool bSame;
while (*cpws1 != L''/0'')
{
bSame = true;
if (*cpws1 != *s2)
{
ch1 = towlower(*cpws1);
ch2 = towlower(*s2);
if (ch1 == ch2)
bSame = true;
}
if (true == bSame)
{
cpws1_ = cpws1;
cpws2 = s2;
while (*cpws1_ != L''/0'')
{
ch1 = towlower(*cpws1_);
ch2 = towlower(*cpws2);
if (ch1 != ch2)
break;
cpws2++;
if (*cpws2 == L''/0'')
return cpws1_-(cpws2 - s2 - 0x01);
cpws1_++;
}
}
cpws1++;
}
return NULL;
}