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

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

• «Привет, мир» = 0

На расстоянии 2 от него находятся следующие струны:

• «XXllo World» = а
• «HeXXo World» = b
• "Привет, XXrld" = c
• "Hello WorXX" = d

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

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

Считайте, что от c до 0 равно 2, а от c до a равно 1, а 0 ближе, чем a.

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

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

Я говорю это, потому что Левенштейн работает, поскольку он отображает пары строк в метрику, которая может сохранить размерность пространства строк. Что произойдет, если вы попытаетесь сопоставить строки с числами, так это большая потеря размерной информации. Например, скажем, у меня есть строка «кошка», я бы хотел, чтобы «летучая мышь», «шляпа», «крыса», «может», «кроватка» и т. Д. Были достаточно близки к этому. При большом количестве слов в результате получается, что разнородные слова встречаются довольно часто, например «летучая мышь» и «кроватка» могут быть близки, потому что они оба находятся на одинаковом расстоянии от «кошки» с положительной стороны. Это похоже на проблему того, что происходит, когда вы пытаетесь сопоставить плоскость с линией, трудно выполнить ограничение, согласно которому точки, расположенные далеко в плоскости, остаются далеко на линии. Таким образом, результатом этого является то, что требование «Чем больше« разных »двух заданных строк, тем больше должно быть разных двух соответствующих значений», является трудным.

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

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

Итак, здесь я надеюсь показать основную проблему и решение.

Проблема: вы правы, что ищете «достаточно хорошее» решение, поскольку получить идеальное решение невозможно (я могу показать это в теории информации, но я выберу геометрию, так как она более читабельна. ). У вас есть N-мерное пространство, поэтому метрики расстояния не могут быть спроецированы без потери информации:

distance projected onto X: (x,y,z).(1,0,0) = x

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

(30,0,0).(1/3,1/3,1/3) = (0,30,0).(1/3,1/3,1/3) = (0,0,30).(1/3,1/3,1/3) = 10

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

Для быстрого решения я предлагаю использовать расстояние Левенштейна из трех описанных ниже строк быстро пытается выполнить PCA в голове:

"acegikmoqsuwy" //use half your permitted symbols then repeat until you have a string of size equal to your longest string.
"bdfhjlnprtv" //use the other half then repeat as above.
"" //The empty string, this will just give you the length of the string, so a cheap one.

Кроме того, если вы хотите углубиться, вам может помочь эта метрика / расстояния: http://www.springer.com/matMathematics/geometry/book/978-3-642-00233-5

и демонстрация расстояния Левенштейна: http://www.merriampark.com/ld.htm

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

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

Измерьте расстояние редактирования от пустой строки, но вместо того, чтобы рассматривать каждое редактирование как имеющее значение «1», дайте ему индекс добавляемой / удаляемой буквы в алфавите, отсортированный по частоте использования (etaoinshrdlu ...), и разница между буквенными индексами, если ваш алгоритм позволяет обнаруживать замены как замены, а не как пары вставка + удаление.

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

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

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

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

Сходство между двумя словами можно вычислить по косинусному сходству между векторами слов. Вы также можете сохранить векторы преобразования SVD, чтобы получить сокращенный вектор для слов, даже ранее невидимых.

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

Вы все еще можете использовать расстояние Левенштейна, но взять его из фиксированной строки «Origin». Например, вы можете использовать строку произвольной длины, состоящую из всех пробелов, в качестве исходной строки.

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

Это ответ на вопрос "с головы до ног".

По сути, это вычисляет расстояние, которое предложение 2 отличается от предложения 1, как декартово расстояние от предложения 1 (предполагается, что оно находится в начале координат), где расстояния являются суммой минимальной разницы Левенштейна между словом в 2 предложениях. Он обладает тем свойством, что 2 равных предложения дают нулевое расстояние.

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

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];
        }
    }
}