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

Ответ 1

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

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

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

и алгоритм Aho-Corasick может сработать для вас

Как долго сохраняются записи?

EDIT:

Это ненужное переключение - ваше сравнение является симметричным по первому массиву и второму изображению

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

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

return findLongest? значение: (firstArray.Length > secondArray.Length)? значение /secondArray.length: значение/firstArray.Length);

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

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

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

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

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

Ответ 5

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

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.

Ответ 6

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

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

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: Ключ к скорости здесь заключается в том, что Словарь будет использовать HashCode ключа, который он хранит, и хэш-функция .net для строк отлично.

Обновление

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

Ответ 7

Здесь другой подход. Я предполагаю, что когда вы сравниваете 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

Ответ 8

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

Измените предложения для слов в строке предложения.

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

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

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