Сравнить несколько строк, и отсеять одинаковые

@EveKS · Регистрация: 19.04.2016

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

Как бы вы ускорили данный вариант, или какие способы вы знаете?

C#

Func<string, IEnumerable<string>> getKey = str => Regex.Split(str, @"[.!?()\[\]{}\n]")
    .Where(s => !string.IsNullOrWhiteSpace(s))
    .Distinct();
 
items = items
    .Where((item, i) =>
    {
        var key1 = getKey(item.Text);
        var isAdd = items
        .Where((_, j) => i != j)
        .All(it =>
        {
            var key2 = getKey(it.Text);
            var ex12 = key1.Except(key2);
            var ex21 = key2.Except(key1);
            var middle = ((double)ex12.Count() + ex21.Count()) / 2;
            var add = (1 - middle / key1.Count()) < 0.9;
            return add;
        });
        return isAdd;
    })
    .ToList();

В принципе, алгоритм можно переделать под цикл внутри цикла, что ускорит процесс...
Если я начну сравнивать 5000+ текстов, это займет не мало времени.

@Jexio · 04.07.2017, 13:29

EveKS, нужно точное вхождение ? есть же алгоритмы по типу Кнута-Морриса-Пратта

@EveKS · 04.07.2017, 13:58 **[ТС]**

Jexio, сейчас я разбиваю на предложения, используя символы [.!?()\[\]{}\n], затем убираю повторы предложений, затем нахожу количество различных предложений между первым и вторым предложением, затем наоборот(2-1), нахожу среднеарифметическое, затем процент совпавших предложений относительно этого среднеарифметического, и если это более 90%, текст исключается.

@Jexio · 04.07.2017, 14:14

EveKS, я не знаю корректны ли ваши 90% , вам виднее, но это задача нечеткого поиска и я знаю только три варианта - Расстояние Левенштейна с различными модификациями , суффиксные деревья(но вам видимо не подойдут из-за большого объема информации) и хэширование по сигнатуре(как раз для большого объема строк). Думаю это лишь малая часть.

@EveKS · 04.07.2017, 14:31 **[ТС]**

Jexio, назвал тему не верно. Сравниваться будут тексты. 90%, там должны оба текста совпасть, случай вхождения части текста в другой текст, большего объема, допускается. (эти алгоритмы посмотрю)

@Jexio · 04.07.2017, 14:46

EveKS, Тогда вам нужен алгоритм longest common subsequence. Всякие утилиты для сравнения файлов вроде на нем построены. Думаю, в скорости с вашим решением выиграет, хотя реализацию я не помню уже, могу и наврать)

@Diamante · 05.07.2017, 01:04

а задача то какой? типа антиплагиат? "мама мыла раму" и " мама раму мыла" и "раму мыла мама" как считать?

@EveKS · 05.07.2017, 08:07 **[ТС]**

Diamante, как бы это 3 разных предложения.

@Jexio 1 / 1 / 1 Регистрация: 22.11.2015 Сообщений: 139
	04.07.2017, 13:29	2
	EveKS, нужно точное вхождение ? есть же алгоритмы по типу Кнута-Морриса-Пратта 0

@EveKS 601 / 485 / 185 Регистрация: 19.04.2016 Сообщений: 1,885
	04.07.2017, 13:58 [ТС]	3
	Jexio, сейчас я разбиваю на предложения, используя символы `[.!?()\[\]{}\n]`, затем убираю повторы предложений, затем нахожу количество различных предложений между первым и вторым предложением, затем наоборот(2-1), нахожу среднеарифметическое, затем процент совпавших предложений относительно этого среднеарифметического, и если это более 90%, текст исключается. 0

@Jexio 1 / 1 / 1 Регистрация: 22.11.2015 Сообщений: 139
	04.07.2017, 14:14	4
	EveKS, я не знаю корректны ли ваши 90% , вам виднее, но это задача нечеткого поиска и я знаю только три варианта - Расстояние Левенштейна с различными модификациями , суффиксные деревья(но вам видимо не подойдут из-за большого объема информации) и хэширование по сигнатуре(как раз для большого объема строк). Думаю это лишь малая часть. 0

@EveKS 601 / 485 / 185 Регистрация: 19.04.2016 Сообщений: 1,885
	04.07.2017, 14:31 [ТС]	5
	Jexio, назвал тему не верно. Сравниваться будут тексты. 90%, там должны оба текста совпасть, случай вхождения части текста в другой текст, большего объема, допускается. (эти алгоритмы посмотрю) 0

@Jexio 1 / 1 / 1 Регистрация: 22.11.2015 Сообщений: 139
	04.07.2017, 14:46	6
	Сообщение было отмечено EveKS как решение Решение EveKS, Тогда вам нужен алгоритм longest common subsequence. Всякие утилиты для сравнения файлов вроде на нем построены. Думаю, в скорости с вашим решением выиграет, хотя реализацию я не помню уже, могу и наврать) 0

@Diamante 3560 / 2501 / 1174 Регистрация: 14.08.2016 Сообщений: 8,206
	05.07.2017, 01:04	7
	а задача то какой? типа антиплагиат? "мама мыла раму" и " мама раму мыла" и "раму мыла мама" как считать? 0

@EveKS 601 / 485 / 185 Регистрация: 19.04.2016 Сообщений: 1,885
	05.07.2017, 08:07 [ТС]	8
	Diamante, как бы это 3 разных предложения. 0

Сравнить несколько строк, и отсеять одинаковые

Решение