Самый быстрый способ выполнить поиск подстроки без учета регистра в C / C ++?

Question

Примечание

Следующий вопрос был задан в 2008 году о некотором коде 2003 года. Как показывает обновление OP , весь этот пост был устаревшим из-за устаревших алгоритмов 2008 года и сохраняется здесь только как историческое любопытство.

---

Мне нужно сделать быстрый поиск подстроки без учета регистра в C / C ++. Мои требования следующие:

• Должен вести себя как strstr () (т.е. возвращать указатель на точку совпадения).
• Должно быть без учета регистра (doh).
• Должен поддерживать текущую локаль.
• Должен быть доступен в Windows (MSVC ++ 8.0) или легко переноситься в Windows (т. Е. Из библиотеки с открытым исходным кодом).

Вот текущая реализация, которую я использую (взята из библиотеки 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, berg@pool.informatik.rwth-aachen.de */

/*
 * Modified to use table lookup instead of tolower(), since tolower() isn't
 * worth s*** on Windows.
 *
 * -- Anders Sandvig (anders@wincue.org)
 */

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

Можете ли вы сделать этот код быстрее или вам известна лучшая реализация?

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

Обновление

Просто чтобы прояснить ситуацию - если это еще не было - я не писал эту функцию, она является частью библиотеки GNU C. Я изменил его только для учета регистра.

Также, спасибо за подсказку о strcasestr() и проверке других реализаций из других источников (таких как OpenBSD, FreeBSD и т. Д.). Кажется, это путь. Код выше взят из 2003 года, поэтому я разместил его здесь в надежде на лучшую доступную версию, которая, очевидно, так и есть. :)

Answer 1

Код, который вы разместили, примерно вдвое быстрее 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

Функция main была:

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

Он был соответствующим образом модифицирован для тестирования обеих реализаций. Я замечаю, что набирая это, я оставил вызов init_stristr, но это не должно слишком сильно что-то менять. bench - это простой сценарий оболочки:

#!/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 2

Вы можете использовать функцию StrStrI, которая находит первое вхождение подстроки в строке. Сравнение не чувствительно к регистру. Не забудьте включить его заголовок - Shlwapi.h. Проверьте это: http://msdn.microsoft.com/en-us/library/windows/desktop/bb773439(v=vs.85).aspx

Answer 3

Для независимого использования платформы:

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

Answer 4

использовать буст-строку algo . Он доступен, кроссплатформенный, и только заголовочный файл (нет библиотеки для ссылки). Не говоря уже о том, что вы все равно должны использовать boost.

#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 5

Почему вы используете _strlwr (строка); в init_stristr ()? Это не стандартная функция. Предположительно это для поддержки локали, но так как это не стандартно, я бы просто использовал:

char_table[i] = tolower(i);

Answer 6

Это не будет учитывать локаль, но если вы можете изменить IS_ALPHA и TO_UPPER, вы можете сделать это, чтобы рассмотреть его.

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

Предполагая, что обе входные строки уже строчные.

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

Вы также можете попробовать использовать маски ... если, например, большинство строк, которые вы собираетесь сравнивать, содержат только символы от a до z, возможно, стоит сделать что-то подобное.

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

Тогда ...

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 8

Я бы посоветовал вам воспользоваться распространенной реализацией strcasestr, которая уже существует. Например, glib, glibc, OpenBSD, FreeBSD и т. Д. Вы можете искать больше с google.com/codesearch. Затем вы можете сделать некоторые измерения производительности и сравнить различные реализации.

Answer 9

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

Стоит ли выигрыш в производительности - это совсем другой вопрос. Для 99% приложений ответ «Нет, оно того не стоит». Ваше приложение может быть одним из крошечных меньшинств, где оно имеет значение. Скорее всего, это не так.

Answer 10

Если вы хотите сбросить циклы ЦП, вы можете подумать об этом - давайте предположим, что мы имеем дело с ASCII, а не с Unicode.

Создать статическую таблицу с 256 записями. Каждая запись в таблице - 256 бит.

Чтобы проверить, равны ли два символа, вы делаете что-то вроде этого:

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

Чтобы построить таблицу, вы устанавливаете бит повсюду в таблице [char1], где вы считаете, что она соответствует char2. Таким образом, при построении таблицы вы должны установить биты в индексе для «а» и «А» в «а» записи (и «А» записи).

Теперь поиск по битам будет медленным (поиск по битам, скорее всего, будет сдвиг, маска и добавление), так что вы можете использовать вместо этого таблицу байтов, чтобы использовать 8 бит для представления 1 бита. Это займет 32 КБ - так что ура - вы нашли компромисс между временем и пространством! Возможно, мы захотим сделать таблицу более гибкой, поэтому допустим, что мы сделаем это вместо этого - вместо таблицы будет определена конгруэнция.

Два символа считаются конгруэнтными тогда и только тогда, когда есть функция, которая определяет их как эквивалентные. Таким образом, «А» и «А» являются конгруэнтными для нечувствительности к регистру. 'A', '& Agrave;', '& Aacute;' и 'В' соответствуют диакритической нечувствительности.

Таким образом, вы определяете битовые поля, которые соответствуют вашим конгруэнтности

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

Тогда ваш тест выглядит примерно так:

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

#define CaseInsensitiveCharEqual(c1, c2) CharsAreCongruent(c1, c2, kCongruentCase)

Этот тип немного возиться с огромными таблицами, к слову, является сердцем ctype.