Более быстрый алгоритм сравнения строк в c #

Question

У меня есть два предложения, которые нужно сравнить друг с другом.Окончательный результат - сколько процентов содержится в одном предложении в другом, моя проблема в том, что у меня есть 100 000 записей, которые нужно сравнить с, скажем, еще 10. Это 1. 000 000 циклов, что в моем алгоритме очень медленное.

Это алгоритм, который я использую:

private double BreakStringsAndCheck(string s1, string s2)
{
    if (s1 == null || s2 == null || s1.Length == 0 || s2.Length == 0)
        return (double)0;
    string[] firstArray = s1.Split(' ');
    string[] secondArray = s2.Split(' ');
    if (firstArray.Length > secondArray.Length)
    {
        string[] tempArray = firstArray;
        firstArray = secondArray;
        secondArray = tempArray;
    }
    double value = 0;
    for (int i = 0; i < firstArray.Length; i++)
        for (int j = 0; j < secondArray.Length; j++)
            value += firstArray[i] == secondArray[j] ? (double)100 : (double)0;
    return findLongest ? value : value / firstArray.Length;
}

Это небольшой метод, но он не очень быстрый.Из моего тестирования я могу сделать 40-60 сравнений за 1 секунду, то есть почти 5 часов для 1.000.000 циклов.

Может кто-нибудь придумать другой метод или логику, которая намного быстрее, чем эта?

Обновление:

Я постараюсь объяснить проблему более подробно.У меня есть база данных с более чем 100 000 записей, и я каждый день вставляю и сравниваю 10-20 новых записей в этой базе данных.Эти записи представляют собой предложения от 2 до 10 слов, и мне нужно написать быстрый метод, который будет сравнивать эти новые записи с записями в базе данных. Результат должен быть в процентах от того, сколько одно предложение содержит слова из другого.

Мне нужны записи с более чем 70% совпадением слов.

Надеюсь, теперь все ясно.

Answer 1

Я не программист на C #, но вот несколько общих советов:

1. Переместить арифметику с плавающей запятой из цикла. Вы должны быть в состоянии сосчитать символы, которые соответствуют, и выполнить деление позже.
2. Вы должны иметь возможность запускать каждый «длинный» цикл в отдельном потоке выполнения, поскольку данные являются статическими. Я бы создал отдельную ветку для каждого из ваших «10» предложений и выполнял бы их параллельно.
3. Вы можете удалить вызов на split, если можете. В основном удалите все дополнительные выделения памяти.

Последняя мысль - взять книгу алгоритмов или Google для алгоритмов обработки текста. Эта проблема звучит как нечто, что было решено снова и снова. Возможно, в AOCP v3 есть что-то, что решает эту проблему. Вы также можете профилировать код (не уверен, какие типы профилировщиков доступны), но это, вероятно, не принесет существенных улучшений.

Answer 2

Лично я бы избегал создания двух массивов; распределение памяти приведет к снижению производительности.

Попробуйте посмотреть на строку string.IndexOf , чтобы узнать, где находится следующий пробел в обеих строках, вычтите его из предыдущего пробела, чтобы определить длину слова. Если две длины равны, тогда используйте string.Compare , чтобы увидеть, равны ли две подстроки. Это позволит избежать выделения памяти и выполнять итерацию строк только один раз, поэтому должно быть быстрее.

Кроме того, как уже упоминали другие, определенно обратите внимание на использование расширений Parallel.

Answer 3

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

Answer 4

Поскольку данные в базе данных, вы не можете сделать работу в базе данных?

Разбейте предложения на слова в строке предложений.

Присоединяй свои слова к расколотым словам. Это должно позволить вам увидеть, какие предложения имеют подходящее слово.

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

Я бы хотел заранее уничтожить ваши данные. Используйте их в качестве индексов для вашей основной таблицы предложений.

Answer 5

Вот другой подход.Я предполагаю, что когда вы сравниваете 10 предложений против 100 000 предложений, будет большое число, в котором нет слов и% = 0. Вместо того, чтобы всегда выполнять 100 000 сравнений, найдите эти предложения в 100 000где хотя бы одно слово соответствует и сравнивает их.

Создайте (один раз) словарь всех слов в 100'000 предложениях.

Каждая запись представляет собой список L предложений, содержащихслово.

tobetested=empty
For each s in the 10 sentences
  for each word in s
    if dictionary.contains(word) then
      add members of L that aren't already there to tobetested
  next
  for each sentence to tobetested ' hopefully much less than 100'000
    compare using your algorithm
  next
next

Answer 6

Попробуйте это.

Перед выполнением любых сравнений предварительно обработайте 100 000 строк.Каждое слово в 100 000 строк будет ключом в объекте Dictionary<>, значение будет представлять собой список идентификаторов (идентификаторы каждой строки, в которой встречается слово), например,

Dictionary<string, List<int>> allWords

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

Dictionary<int, int> matches

Вы разбиваете строку поиска на слова, и для каждого идентификатора строки для каждого слова вы увеличиваете значение для идентификатора этой строки.

var searchWords = search.Split(" ");
foreach(var word in searchWord)
{
    foreach(var id in allWords[word])
        matches[id] += 1;
}
var bestRowId = (from m in matches orderby m.Value select m.Key).Last();

Идентификатор строки с наибольшимзначение является лучшим соответствием.

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

NB: Ключ к скорости здесь в том, что Dictionary будет использовать HashCode ключа, который он хранит, и хеш-функция .net для строк отлично.

Обновление

Если предварительная обработка для этого заказа занимает слишком много времени, то вы можете выполнить более легкую предварительную обработку.
Когда вы читаете каждую из 100 000 строк, разбейте ее на слова,и отсортировать массив слов.Затем, когда вы сравниваете, разбиваете строку для сравнения и сортируете ее тоже.Ваша функция экономит время, потому что она не разбивает каждую строку несколько раз, и ваши вложенные циклы могут быть заменены циклом для min(words1.length, words2.length).

Answer 7

Пример пересечения

private double BreakStringsAndCheck(string s1, string s2)
{
    var split1 = s1.Split(' ');
    return (double)split1.Intersect(s2.Split(' ')).Count() / split1.Count() * 100.0;
}

Я бы предпочел вернуть коэффициент 0,4 вместо 40,0 для:

var percent = BreakStringsAndCheck("Jan Banan går till GAIS.", "I Torsk på Tallin så var en annan Jan Banan med.");

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

var percent = BreakStringsAndCheck("I Torsk på Tallin så var en annan Jan Banan med.", "Jan Banan går till GAIS.");

но мой пример пересечения вернётся 18.18. Я чувствую, что это более правильно, но если вы действительно хотите, чтобы ваш путь, то просто добавьте

if (s1.Length > s2.Length)
{
    var tmp = s2;
    s2 = s1;
    s1 = tmp;
}

к началу метода.

Presplitting

var presplits = new List<string[]>() { s1.Split(' '), s2.Split(' '), s3.Split(' ') };

...

private static IEnumerable<double> StringsInString(IEnumerable<string[]> strings, string s2)
{
    return strings.Select(h => (double)h.Intersect(s2.Split(' ')).Count() / h.Count());
}

затем зациклите все свои 100.000 строк в Parallel.For.

PS. Я думаю, что вам нужно будет уменьшить или удалить ., , и так далее из строк, чтобы получить более правильное соотношение. DS.

Answer 8

Если сначала разбить 10 записей, то вы найдете небольшое количество строк во многих больших строках. Это, кажется, подходит http://en.wikipedia.org/wiki/String_searching_algorithm#Algorithms_using_finite_set_of_patterns

и алгоритм Aho-Corasick могут хорошо работать для вас

Как долго записи?

EDIT:

Это ненужный переход - ваше сравнение симметрично относительно firstArray и secondArray

 if (firstArray.Length > secondArray.Length)
    {
        string[] tempArray = firstArray;
        firstArray = secondArray;
        secondArray = tempArray;
    }

вместо этого замените возврат на

вернуть findLongest? значение: (firstArray.Length> secondArray.Length)? value / secondArray.length: value / firstArray.Length);

только с чем-то более читабельным:)

ОБНОВЛЕНИЕ после обновления вопроса

Таким образом, вы могли бы предварительно обработать 100 000 (например, хэшировать слова)? И только 10-20 изменений в день, поэтому обновление предварительно обработанных данных будет простым.

Вам определенно нужно сделать что-то, что использует относительно статическую природу 100000. Даже если вы выполняли предварительную обработку только один раз в день, вы можете выполнить сравнение со всеми записями за последние дни, а затем использовать текущий медленный подход для всех остальных, добавленных с момента последнего запуска предварительной обработки. Из того, что вы говорите, будет не более 10-20 из этих

Я думаю, что либо идея хеширования, либо создание трюка с ахо-комизаком из корпуса даст вам гораздо более быстрый поиск.