“Абсолютная” строковая метрика

Я не думаю, что это возможно сделать. Запустите с простой строки и присвойте ей нуль (действительно не имеет значения, что число),

• "Привет Мир" = 0

Следующие строки на расстоянии 2 от него:

• "Мир XXllo" = a
• "Мир HeXXo" = b
• "Привет XXrld" = c
• "Привет WorXX" = d

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

a = 1, b =-1, c = 2, d =-2

Полагайте, что c к 0 равняется 2, все же c к 1, все же 0 ближе, чем a.

И это - просто простой случай.

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

Я говорю это, потому что Levenstein работает, так как это отображает пар строк к метрике, которая может сохранить размерность строкового пространства. Что происходит, при попытке отобразиться, строки к числам то, что существует большая потеря размерной информации. Например, скажите, что у меня есть строка "кошка", я хотел бы "летучую мышь", "шляпа", "крыса", "может", "раскладушка" и т.д. ко всем быть обоснованно близко к этому. С большим количеством слов результат состоит в том, что Вы заканчиваете с отличающимися словами, являющимися близким относительно часто, например, "летучая мышь", и "раскладушка" может быть близкой, потому что они оба, оказывается, подобные расстояния от "кошки" на положительной стороне. Это подобно проблеме того, что происходит, когда Вы пытаетесь отобразить плоскость на строку, трудно встретить ограничение, которое указывает далеко в плоском пребывании далеко на строке. Так, результат этого - то, что, 'Чем более "различные" две данных строки, тем более различные два соответствующих значения должны быть' требованием, является трудным.

Так, мое первое предложение, Вам действительно нужно что-то, что делает это, простой хэш-код будет достаточен, чтобы дать Вам уникальные значения, или возможно можно ли использовать Levenstein, в конце концов, и проигнорировать ли значения для отдельных строк? Если ни один из тех не достаточен, возможно, можно использовать многомерное значение функции, которое является строками карты в пар, утраивается или другой маленький кортеж чисел. Дополнительная размерность допустила, что путь даст Вам намного лучшие результаты.

Пример мог бы кодировать строку тройным: длина, сумма значений букв в строке, переменная сумма значений букв, например, f ("кошка") = (3, 3 + 1 + 20, 3 - 1 + 20) = (3, 24, 22). Это имело бы некоторые свойства, которых Вы требуете, но вероятно не оптимально. Попытайтесь искать ортогональные функции строки, чтобы сделать это кодирование, или еще лучше, если у Вас есть большой набор тестов строк существуют существующие библиотеки для отображения этого вида данных в низкие размеры при сохранении метрик (например, метрика Levenstein), и можно обучить функцию на этом. Я помню, что язык S имел поддержку этого вида вещи.

Я хотел бы развернуть ответ FryGuy, почему он не собирается работать в любом постоянном числе размеров. Давайте возьмем aaaaaaaaaa и baaaaaaaaa, abaaaaaaaa, ... , aaaaaaaaab. В этом примере строки имеют длину 10, но они могут иметь произвольную длину. Расстояние каждого из 10 b- строки от aaaaaaaaaa 1, и их расстояние друг от друга равняется 2. В целом при взятии починенных строк длины N по алфавиту с 2 буквами их график расстояния является N-мерным гиперкубом.

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

Для преобладания над 'относительным расстоянием' проблема все, что необходимо сделать, является взятием фиксированная точка для измерения от.

Вы могли все еще использовать расстояние Levenstein, но взять его от фиксированной строки "Источника". Например, Вы могли использовать строку произвольной длины всех пробелов как Ваша строка источника.

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

Измерьте расстояние редактирования от пустой строки, но вместо того, чтобы рассматривать каждое редактирование как наличие значения "1", дайте его, индекс буквы того, чтобы быть добавил/удалил в алфавите, отсортированном по частоте использования (etaoinshrdlu...), и различие между индексами буквы, если Ваш алгоритм позволяет Вам обнаруживать замены как замены, а не как insert+delete пары.

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

Ваши размеры являются продуктом элементов Вашего алфавита и положений в строке. Учитывая алфавит ("a", "b", "c", "t") и максимальная длина 3, размеры (a:1, b:1, c:1, t:1..., a:3, b:3, c:3, t:3)

Как пример, "cat" становится (0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1).

Это - конечно, огромный набор данных, но можно использовать методы сокращения размерности (как SVD) для сокращения количества размеров. Это должно работать хорошо, потому что существует много повторяющихся шаблонов в словах. Можно настроить количество выходных размеров для удовлетворения потребностям.

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

Это "от макушки", отвечают на вопрос.

В основном это вычисляет, предложение расстояния 2 отличается от предложения 1 как Декартово расстояние от предложения 1 (предполагаемый быть в источнике), где расстояния являются суммой минимального различия Levenshtein между словом в этих 2 предложениях. Это имеет свойство, что 2 равных предложения дают 0 расстояний.

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string str1 = "The cat sat on the mat";
            string str2 = "The quick brown fox jumped over the lazy cow";
            ReportDifference(str1, str1);
            ReportDifference(str2, str2);
            ReportDifference(str1, str2);
            ReportDifference(str2, str1);
        }
        /// <summary>
        /// Quick test andisplay routine
        /// </summary>
        /// <param name="str1">First sentence to test with</param>
        /// <param name="str2">Second sentence to test with</param>
        static void ReportDifference(string str1, string str2)
        {
            Debug.WriteLine(
                String.Format("difference between \"{0}\" and \"{1}\" is {2}", 
                str1, str2, Difference(str1, str2))); 
        }
        /// <summary>
        /// This does the hard work.
        /// Basically, what it does is:
        /// 1) Split the stings into tokens/words
        /// 2) Form a cartesian product of the 2 lists of words. 
        /// 3) Calculate the Levenshtein Distance between each word.
        /// 4) Group on the words from the first sentance
        /// 5) Get the min distance between the word in first sentence and all of the words from the second
        /// 6) Square the distances for each word. 
        ///     (based on the distance betwen 2 points is the sqrt of the sum of the x,y,... axises distances
        ///     what this assumes is the first word is the origin)
        /// 7) take the square root of sum
        /// </summary>
        /// <param name="str1">sentence 1 compare</param>
        /// <param name="str2">sentence 2 compare</param>
        /// <returns>distance calculated</returns>
        static double Difference(string str1, string str2)
        {
            string[] splitters = { " " };

            var a = Math.Sqrt(
                (from x in str1.Split(splitters, StringSplitOptions.RemoveEmptyEntries)
                     from y in str2.Split(splitters, StringSplitOptions.RemoveEmptyEntries)
                     select new {x, y, ld = Distance.LD(x,y)} )
                    .GroupBy(x => x.x)
                    .Select(q => new { q.Key, min_match = q.Min(p => p.ld) })
                    .Sum(s =>  (double)(s.min_match * s.min_match )));
            return a;
        }
    }

    /// <summary>
    /// Lifted from http://www.merriampark.com/ldcsharp.htm
    /// </summary>
    public class Distance
    {

        /// <summary>
        /// Compute Levenshtein distance
        /// </summary>
        /// <param name="s">String 1</param>
        /// <param name="t">String 2</param>
        /// <returns>Distance between the two strings.
        /// The larger the number, the bigger the difference.
        /// </returns>
        public static int LD(string s, string t)
        {
            int n = s.Length; //length of s
            int m = t.Length; //length of t
            int[,] d = new int[n + 1, m + 1]; // matrix
            int cost; // cost
            // Step 1
            if (n == 0) return m;
            if (m == 0) return n;
            // Step 2
            for (int i = 0; i <= n; d[i, 0] = i++) ;
            for (int j = 0; j <= m; d[0, j] = j++) ;
            // Step 3
            for (int i = 1; i <= n; i++)
            {
                //Step 4
                for (int j = 1; j <= m; j++)
                {
                    // Step 5
                    cost = (t.Substring(j - 1, 1) == s.Substring(i - 1, 1) ? 0 : 1);
                    // Step 6
                    d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                              d[i - 1, j - 1] + cost);
                }
            }
            // Step 7
            return d[n, m];
        }
    }
}