Пословное сравнение различий двух строк в.NET

Question

Мне нужно сделать слово в слово сравнение двух строк. Что-то вроде diff, но для слов, а не для строк.

Как это сделано в Википедии http://en.wikipedia.org/w/index.php?title=Horapollo&action=historysubmit&diff=21895647&oldid=21893459

В результате я хочу вернуть два массива индексов слов, которые отличаются в две строки.

Есть ли какие-нибудь библиотеки /frameworks/standalone_methods для.NET, которые могут это сделать?

PS хочу сравнить несколько килобайт текста

Answer 1

Кажется, я нашел необходимое решение:

DiffPlex представляет собой комбинацию библиотеки.NET Diffing с Silverlight и средством просмотра различий HTML. http://diffplex.codeplex.com/

Но есть одна ошибка. В этих строках "Hello-Kitty", "Hello - Kitty" слово "Hello" будет помечено как разница. Хотя разница в космическом символе.

Answer 2

На самом деле, вы, вероятно, хотите реализовать вариант алгоритмов Local Alignment/Global Alignment, которые мы используем при выравнивании последовательностей ДНК. Это потому, что вы, вероятно, не можете сделать пословное сравнение двух строк. То есть:

Быстрая коричневая лиса прыгает через ленивую собаку
Быстрая лиса перепрыгивает через ленивую собаку

Другими словами, если вы не можете идентифицировать вставки и удаления целых слов, ваш алгоритм сравнения может стать очень точным. Взгляните на алгоритм Смита-Уотермана и алгоритм Нидлмана-Вунша и найдите способ адаптировать их к вашим потребностям. Поскольку такое пространство поиска может стать очень большим, если строки длинные, вы также можете проверить BLAST. BLAST является очень распространенным эвристическим алгоритмом и в значительной степени стандартом в генетических поисках.

Answer 3

Используйте RegularExpressions.

Как в примере:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Collections.Specialized;

namespace WindowsApplication10
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button2_Click(object sender, EventArgs e)
        {
            decimal discrimation = 0.75M;
            string formHeading = "The brown dog jumped over the red lazy river, and then took a little nap! Fun!";
            string userSearch = "The brown dog jumped over the red lazy river, and then took a little ";
            //string userSearch = "brown dog nap fun";
            decimal res = CompareText(formHeading, userSearch);

            if (res >= discrimation)
            {
                MessageBox.Show("MATCH!" + res.ToString());
            }
            else 
            {
                MessageBox.Show("does not match! " + res.ToString());
            }
        }


        /// <summary>
        /// Returns a percentage of 1 on how many words were matched
        /// </summary>
        /// <returns></returns>
        private decimal CompareText(string formHeading, string userSearch)
        {
            StringCollection formHeadingWords = new StringCollection();
            StringCollection userSearchWords = new StringCollection();
            formHeadingWords.AddRange(System.Text.RegularExpressions.Regex.Split(formHeading, @"\W"));
            userSearchWords.AddRange(System.Text.RegularExpressions.Regex.Split(userSearch, @"\W"));

            int wordsFound = 0;
            for (int i1 = 0; i1 < userSearchWords.Count; i1++)
            {
                if (formHeadingWords.Contains(userSearchWords[i1]))
                    wordsFound += 1;
            }
            return (Convert.ToDecimal(wordsFound) / Convert.ToDecimal(formHeadingWords.Count));
        }
    }
}

Answer 4

Вы можете заменить все слова в ваших 2 текстах уникальными числами, взять готовый код для вычисления расстояния Редактировать и заменить его символьное сравнение на сравнение числа с номером, и все готово!

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

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

Видеть это. http://en.wikipedia.org/wiki/Levenshtein_distance

Answer 5

Вы можете попробовать это, хотя я не уверен, что это то, что вы ищете StringUtils.difference () ( http://commons.apache.org/lang/api-release/org/apache/commons/lang/StringUtils.html)

С другой стороны, проект Eclipse (eclipse.org) имеет функцию сравнения diff, что означает, что они также должны иметь код для определения различий, вы можете просмотреть их API или исходный код, чтобы увидеть, что вы можете найти.

Удачи.

Answer 6

Еще одна библиотека для C# - это diff-match-patch - http://code.google.com/p/google-diff-match-patch/.

Плохо то, что он находит разницу в персонажах. Хорошая вещь, есть инструкция, что вы должны добавить, чтобы изменить слова.

Answer 7

Кажется, я буду использовать алгоритм / порт, используемый здесь

http://www.google.com/codesearch/p?hl=en&sa=N&cd=6&ct=rc