Очень быстрый поиск подстроки

@miachka · Регистрация: 11.08.2010

Author24 — интернет-сервис помощи студентам

Добрый день!

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

Подскажите как ускорить поиск? Хотелось бы готовый алгоритм, библиотеку, класс... Ну и теорию конечно.

@sk007 · 14.07.2011, 16:48

можно так, с Регулярным выражением

C#

if (Regex.IsMatch(InputText.Text, StrokaText.Text))
            {
                RES.Text = "Есть"; //или что еще там
            }

Но, я незнаю быстро ли работает этот код

@Casper-SC · 14.07.2011, 17:13

Покажи что и как делаешь. Возможно тут та же беда, как была в одной теме. Там у человека тоже прога со строками работала, и тормозила не по детски. Помогли ему, стало всё быстро работать.

Добавлено через 1 минуту

Сообщение от miachka

Когда я использую поиск string.Contains() программа работает часами.

Часами... Хм...

@miachka · 14.07.2011, 17:27 **[ТС]**

C#

private bool find_in_text(string f,string s1,string s2, string s3)
{
     bool ok = false;
     string s = "";
     if ((s1 != "") && (s2 != "") && (s3 != ""))
     {
         if (f != "") s = f + " ";
         s = s+s1 + " " + s2 + " " + s3;
         if (text.Contains(s))
             ok = true;
     }
            return ok;
}
 
 
while(пока не нагенерю скока нада)
{
    //если убрать условие, все работает быстро
   if (find_in_text(first, cur_prefix1, cur_prefix2, suf))
   {
    suf = next_word(cur_prefix2, "",suf);
   }
   first = cur_prefix1;
   cur_prefix1 = cur_prefix2;
   cur_prefix2 = suf;
}

@Casper-SC · 14.07.2011, 18:26

А какие значения можно подставить? Чтобы у себя потестить. Вообще приведи пример, чтобы я смог у себя запустить и попробовать ускорить работу, а то догадываться, для чего ты используешь метод как-то напряжно

Добавлено через 18 минут
Попробуй замени на:

C#

        private bool find_in_text(string f, string s1, string s2, string s3)
        {
            StringBuilder sb = new StringBuilder();
            if ((!string.IsNullOrWhiteSpace(s1)) && (!string.IsNullOrWhiteSpace(s2)) && (!string.IsNullOrWhiteSpace(s3)))
            {
                if (!string.IsNullOrWhiteSpace(f)) sb.Append(f).Append(" ");
                sb.Append(sb.ToString()).Append(s1).Append(" ").Append(s2).Append(" ").Append(s3);
                if (text.Contains(sb.ToString()))
                    return true;
            }
            return false;
        }

Не уверен, но возможно чуток ускорится. Зависит от размеров s1, s2, s3, f

Добавлено через 17 минут
Ща потестил, что-то способ с StringBuilder значительно медленнее работает. Ничего не понимаю. Сделал передачу огромных строк, там StringBuilder перегнал пару раз твой способ, но в основном примерно одинаково.

Добавлено через 29 секунд
Вот атк тестил:

C#

        String text = "агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр NNN Привет говорю я тебе агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр агыгурошыгугшпа ыгшщпшг ырупшг ырушпегцр387ейцрн97пгнфыргц90пшщфцпр ";
        private void button1_Click(object sender, RoutedEventArgs e)
        {
            const int quantityIterations = 500000;
            Stopwatch sw1 = new Stopwatch();
            sw1.Start();
            bool text1Searched = false;
            for (int i = 0; i < quantityIterations; i++)
            {
                if (find_in_text("ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg", "Приветggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg", "ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg", "gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg"))
                    text1Searched = true;
            }
            sw1.Stop();
 
            Stopwatch sw2 = new Stopwatch();
            sw2.Start();
            bool text2Searched = false;
            for (int i = 0; i < quantityIterations; i++)
            {
                if (find_in_text2("ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg", "Приветggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg", "ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg", "gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg"))
                    text2Searched = true;
                
            }
            sw2.Stop();
 
            MessageBox.Show(string.Format("StringBuilder способ отработал за: {0} Миллисекунд\n" +
                                          "Старый способ отработал за: {1} Миллисекунд", sw1.ElapsedMilliseconds, sw2.ElapsedMilliseconds));
        }

И то метод я переделал вот так:

C#

        StringBuilder sb = new StringBuilder();
        private bool find_in_text(string f, string s1, string s2, string s3)
        {
            sb.Clear();
            if ((!string.IsNullOrWhiteSpace(s1)) && (!string.IsNullOrWhiteSpace(s2)) && (!string.IsNullOrWhiteSpace(s3)))
            {
                if (!string.IsNullOrWhiteSpace(f)) sb.Append(f).Append(" ");
                sb.Append(sb.ToString()).Append(s1).Append(" ").Append(s2).Append(" ").Append(s3);
                if (text.Contains(sb.ToString()))
                    return true;
            }
            return false;
        }

Добавлено через 16 минут
С регулярками тоже тестил, тоже намного дольше работает, по крайней мере если делать как советовали выше.

@miachka · 15.07.2011, 14:23 **[ТС]**

Casper-SC, очень извиняюсь, но мне начальник не разрешает выкладывать исходники.
Попробовала твой метод, особой разницы в скорости не заметила, в лучшую сторону, по крайней мере.
Вообще я пишу генератор текста.
парметры - text=длинный текст; f, s1, s2, s3 - как-бы случайные слова, но не совсем.
функция find_in_text проверяет есть ли в тексте фраза f+s1+s2+s3. Без проверки на совпадение с текстом, работает все быстро, но порог плагиата около 30%. Проверка значительно снижает плагиат.

Набросала вот такой класс, памяти он жрет много, но скорость программы увелилилась раза в 2,5 примерно. words_dict это что-то типа дерева, но на словарях. На шарпе ни разу не работала с памятью, сто лет давно в институте была лаба архиватор на паскале, но там вроде была работа с указателями.

В худшем случае мне нужно ускорить алгоритм поиска еще раза в 4, в лучшем -...

C#

class FastSearch
    {
        Dictionary<string, Dictionary<string, Dictionary<string, StringCollection>>> words_dict = new Dictionary<string, Dictionary<string, Dictionary<string, StringCollection>>>();
 
        public FastSearch(string text)
        {
 
            text = text.Replace(",", " ,");//чтобы запятая была словом
            text = text.Replace(".", " .");
            string[] words = text.Split(new char[]{' '} ,System.StringSplitOptions.RemoveEmptyEntries);
            string pref1 = words[0];
            string pref2 = words[1];
            string pref3 = words[2];
            string suf;
            for (int i = 3; i < words.Count(); i++)
            {
                suf = words[i];
                if (!words_dict.ContainsKey(pref1))
                {
                    StringCollection sc = new StringCollection();
                    sc.Add(suf);
                    Dictionary<string, StringCollection> d1 = new Dictionary<string, StringCollection>();
                    d1.Add(pref3, sc);
                    Dictionary<string, Dictionary<string, StringCollection>> d2 = new Dictionary<string, Dictionary<string, StringCollection>>();
                    d2.Add(pref2, d1);
                    words_dict.Add(pref1, d2);
                }
                else if (!words_dict[pref1].ContainsKey(pref2))
                {
                    StringCollection sc = new StringCollection();
                    sc.Add(suf);
                    Dictionary<string, StringCollection> d1 = new Dictionary<string, StringCollection>();
                    d1.Add(pref3, sc);
                    words_dict[pref1].Add(pref2, d1);
                }
                else if (!words_dict[pref1][pref2].ContainsKey(pref3))
                {
                    StringCollection sc = new StringCollection();
                    sc.Add(suf);
                    words_dict[pref1][pref2].Add(pref3, sc);
                }
                else if (!words_dict[pref1][pref2][pref3].Contains(suf))
                    words_dict[pref1][pref2][pref3].Add(suf);
                pref1 = pref2;
                pref2 = pref3;
                pref3 = suf;
            }
 
        }
 
        public bool find(string s1,string s2,string s3,string s4)
        {
            if (words_dict.ContainsKey(s1))
            {
                if (words_dict[s1].ContainsKey(s2))
                {
                    if (words_dict[s1][s2].ContainsKey(s3))
                    {
                        if (words_dict[s1][s2][s3].Contains(s4))
                            return true;
                        else return false;
                    }
                    else return false;
                }
                else return false;
            }
            else return false;
       }
}

C#

private bool find_in_text(string f, string s1, string s2, string s3)
{
            
    if (fs.find(f,s1,s2,s3)) return true;
    else return false;
 
}

Добавлено через 16 минут
Вот пришла мысль, может хеширование заюзать. Тогда не нужно будет кучу дублирующихся слов хранить в памяти. Но только вот какую функцию хеширования использовать, чтобы было быстро ее вычислять, и чтобы не было много дублей.

@Killster · 15.07.2011, 20:03

Сообщение от miachka

Добавлено через 16 минут
Вот пришла мысль, может хеширование заюзать. Тогда не нужно будет кучу дублирующихся слов хранить в памяти. Но только вот какую функцию хеширования использовать, чтобы было быстро ее вычислять, и чтобы не было много дублей.

Можно использовать встроенный в HashTable. А вообще я рекомендую Adler32 - работает очень быстро и могу скинуть реализацию.

@агерон · 16.07.2011, 07:28

могу предложить такую идею

C#

//список хеш сум всех строк текста где ищеться совпадение  
List<int> hash = new List<int>();
 
bool GenerationHashString()
{
   string result=string.Empty;
   //
   //генерация строки
   //
   return (hash.IndexOf(result.GetHashCode()) > 0);//поиск существования строки 
}

фактически для работы алгоритма следует заполнить hash хешами (через вызовы GetHashCode()) всех строк 1 раз и время поиска существования строки будет равно const
для более развернутого ответа мне нужно знать где располагается исходный текст в памяти или в файле?

@Killster · 16.07.2011, 11:48

Сообщение от агерон

фактически для работы алгоритма следует заполнить hash хешами (через вызовы GetHashCode()) всех строк 1 раз и время поиска существования строки будет равно const

Если время взятия хеша o(1) (так оно и есть), то для взятия хеша всех подстрок нам понадобится n! времени. Для большого текста это ОЧЕНЬ неприемлемо, будет занимать ОГРОМНОЕ количество памяти..
Надо что-то придумывать с кешем.

Добавлено через 4 минуты
Кстати, если понадобится, GetHashCode из исходников:

C#

public override int GetHashCode()
        {
            unsafe
            {
                fixed (char* src = this)
                {
                    int hash1 = (5381<<16) + 5381; 
                    int hash2 = hash1;
 
                    int* pint = (int *)src;
                    int len = this.Length; 
                    while(len > 0) { 
                        hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0];
                        if( len <= 2) { 
                            break;
                        }
                        hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ pint[1];
                        pint += 2; 
                        len  -= 4;
                    } 
                    return hash1 + (hash2 * 1566083941);
                }
            }
        }

@miachka 4 / 4 / 0 Регистрация: 11.08.2010 Сообщений: 28
		1
	Очень быстрый поиск подстроки 14.07.2011, 16:23. Показов 7798. Ответов 8 Метки нет (Все метки) Добрый день! На каждом шаге программы генерируется строка, нужно проверить есть ли она в исходном тексте. Шагов очень много, текст длинный. Когда я использую поиск string.Contains() программа работает часами. Подскажите как ускорить поиск? Хотелось бы готовый алгоритм, библиотеку, класс... Ну и теорию конечно. 0

@Casper-SC 4432 / 2092 / 404 Регистрация: 27.03.2010 Сообщений: 5,657 Записей в блоге: 1
	14.07.2011, 17:13	3
	Покажи что и как делаешь. Возможно тут та же беда, как была в одной теме. Там у человека тоже прога со строками работала, и тормозила не по детски. Помогли ему, стало всё быстро работать. Добавлено через 1 минуту Сообщение от miachka Когда я использую поиск string.Contains() программа работает часами. Часами... Хм... 0

@Killster 185 / 188 / 17 Регистрация: 26.11.2010 Сообщений: 511
	15.07.2011, 20:03	7
	Сообщение от miachka Добавлено через 16 минут Вот пришла мысль, может хеширование заюзать. Тогда не нужно будет кучу дублирующихся слов хранить в памяти. Но только вот какую функцию хеширования использовать, чтобы было быстро ее вычислять, и чтобы не было много дублей. Можно использовать встроенный в HashTable. А вообще я рекомендую Adler32 - работает очень быстро и могу скинуть реализацию. 0

	16.07.2011, 11:48