Исключить сходства в списке строк, чтобы извлечь разницу

avatar
Matt McManis
8 апреля 2018 в 04:10
83
2
0

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

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

(Это пример, это может быть любое короткое предложение со сходством.)

Книга «Повелитель мух» — классика.
Книга «Убить пересмешника» — классика.
Книга «Над пропастью во ржи» — классика.

Проблема, с которой я столкнулся, заключается в том, что я не могу просто использовать regex или Contains(), чтобы найти Заголовок в предложении, потому что я не знаю, каким будет следующее Предложение или Заголовок Книги. Я просматриваю многие из внешних источников, поэтому я подумал, что смогу извлечь то, что находится между похожими словами.

The book named Над пропастью во ржи is a classic.

List<string> sentences = new List<string>() { };
List<string> titles = new List<string>() { };

sentences.Add("The book named Lord of the Flies is a classic.");
sentences.Add("The book named To Kill a Mockingbird is a classic.");
sentences.Add("The book named The Catcher in the Rye is a classic.");

foreach (String title in sentences)
{
    // what to do here?

    // add title to titles list
}

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

Источник
AlphaDelta
8 апреля 2018 в 04:12
3

Наоборот, это кажется идеальным временем для использования регулярных выражений. это то, что вы ищете?

Enigmativity
8 апреля 2018 в 04:16
2

Я правильно понимаю, что в ваших исходных данных у вас много разных префиксов и суффиксов в предложениях, содержащих названия книг? Это не просто "The book named " и " is a classic."?

Matt McManis
8 апреля 2018 в 04:35
0

@Enigmativity Да, это может быть много разных префиксов и суффиксов. Но я всегда добавляю в список похожие совпадающие строки.

Kevin
8 апреля 2018 в 05:12
0

Если ваш список предложений всегда похож, вы можете просто использовать Substring, чтобы получить значение, если нет, создать список префиксов и суффиксов, а затем для каждого предложения выполнить цикл по префиксам и суффиксам, чтобы найти совпадение. Когда вы найдете совпадение, вы можете использовать предложения[x].Substring() для анализа заголовка, используя длину совпадений.

Kevin
8 апреля 2018 в 05:20
0

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

Ответы (2)

avatar
Zohar Peled
8 апреля 2018 в 05:24
3

Это была интересная проблема, поэтому я немного поиграл с ней и нашел следующее (громоздкое) решение:

Найдите первый индекс, в котором любое из предложений имеет другой символ, затем сделайте то же самое в перевернутых предложениях, а затем используйте Substring для извлечения только разных частей предложений: 

List<string> ExtractDifferences(List<string> sentences)
{
    var firstDiffIndex = GetFirstDifferenceIndex(sentences);
    var lastDiffIndex = GetFirstDifferenceIndex(sentences.Select(s => new string(s.Reverse().ToArray())).ToList());
    return sentences.Select(s => s.Substring(firstDiffIndex, s.Length - lastDiffIndex - firstDiffIndex)).ToList();
}


int GetFirstDifferenceIndex(IList<string> strings)
{
    int firstDifferenceIndex = int.MaxValue;

    for (int i = 0; i < strings.Count; i++)
    {
        var current = strings[i];
        var prev = strings[i == 0 ? strings.Count - 1 : i - 1];

        var firstDiffIndex = current
            .Select((c, j) => new { CurrentChar = c, Index = j })
            .FirstOrDefault(ci => ci.CurrentChar != prev[ci.Index])
            .Index;

        if (firstDiffIndex < firstDifferenceIndex)
        {
            firstDifferenceIndex = firstDiffIndex;
        }
    }
    return firstDifferenceIndex;
}

Я думаю, что метод GetFirstDifferenceIndex можно написать по-другому, возможно, лучше использовать linq, но у меня нет достаточно времени, чтобы поиграться с ним.

Вы можете увидеть живую демонстрацию на rextester.

Matt McManis
8 апреля 2018 в 06:39
0

Он хорошо работает в моем проекте. Знаете ли вы, как его можно изменить, чтобы он продолжал работать, если суффикс в строке отсутствует?

Zohar Peled
8 апреля 2018 в 06:54
0

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

Matt McManis
8 апреля 2018 в 07:07
0

Тогда он должен работать нормально. Все они должны быть похожи, поэтому, если в одном из них отсутствует суффикс, будут все.

Zohar Peled
8 апреля 2018 в 07:11
0

Отлично, я рад, что смог помочь. Держу пари, вы знаете, что делать дальше :-)

Kevin
8 апреля 2018 в 15:48
0

Ради эффективности я бы изменил две вещи: 1) не переворачивал строку 2) цикл был бы быстрее, чем запрос linq

Zohar Peled
8 апреля 2018 в 17:03
0

@kevin не беспокойся так о производительности. Пишите код для удобочитаемости. Установите цели производительности и сравните свой код с ними. Если он слишком медленный, найдите узкие места и исправьте их.

Kevin
8 апреля 2018 в 21:52
0

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

Matt McManis
10 апреля 2018 в 02:22
0

@ZoharPeled Я нашел ошибку, я разместил новый вопрос, может быть, вы можете помочь. coderhelper.com/q/49744331/6806643

avatar
w.b
8 апреля 2018 в 16:37
0

Рабочее решение с использованием LINQ:

List<string> sentences = new List<string>() { };
List<string> titles = new List<string>() { };

sentences.Add("The book named Lord of the Flies is a classic.");
sentences.Add("The book named To Kill a Mockingbird is a classic.");
sentences.Add("The book named The Catcher in the Rye is a classic.");
sentences.Add("Hello");
sentences.Add("The book named ");


titles = sentences.Where(sentence => sentence.Length > "The book named ".Length + " is a classic".Length)
            .GroupBy(sentence => sentence.Substring(0, 15), sentence => sentence.Remove(sentence.Length - " is a classic".Length).Substring("The book named ".Length))
            .Where(g => g.Key == "The book named ")
            .SelectMany(g => g)
            .ToList();

foreach (var title in titles)
    WriteLine(title);

Во-первых, он отфильтровывает предложения, слишком короткие для соответствия критериям, затем группирует результаты по первым 15 буквам и извлекает заголовки с помощью String.Remove.