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

Question

У меня огромный (но конечный) набор строк на естественном языке.

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

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

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

Обновление размеров

Я буду рад согласиться на многомерный (лучше 3D) вектор вместо единственного числового значения.

Обновление ожидаемой корректности результата

Как правильно было отмечено здесь и здесь , расстояние от одной строки до другой представляет собой вектор с MAX(firstStringLength, secondStringLength) размерами. Как правило, невозможно уменьшить количество измерений без потери информации.

Однако мне не нужно абсолютное решение. Я бы согласился на любое «достаточно хорошее» преобразование из пространства N-мерных строк в мое трехмерное пространство.

Обратите внимание, что у меня есть конечное число строк конечной длины. (Количество строк довольно велико, около 80 миллионов (10 ГБ), поэтому лучше выбрать какой-нибудь однопроходный алгоритм без состояния.)

Из сканирования ссылок у меня сложилось впечатление, что Кривая заполнения пространства Гильберта может помочь мне здесь. Выглядит как Анализ свойств кластеризации в статье о кривой заполнения пространства Гильберта обсуждается что-то близкое к моей проблеме ...

Обновление на подходе кривой Гильберта

1. Мы отображаем каждую строку в точку в N-мерном пространстве, где N - максимальная длина строки в наборе. Кстати, можно ли здесь использовать i-й символьный код из строки в качестве значения i-й координаты?
2. Мы строим кривую Гильберта через это N-мерное пространство.
3. Для каждой строки мы берем точку на кривой, ближайшую к координатам строки. Значение Гильберта этой точки (длина от начала кривой) является одномерным значением, которое я ищу.
4. Если нам нужно значение 3D, мы строим кривую Гильберта в 3D и выбираем точки, соответствующие значениям Гильберта, рассчитанным выше.

Это выглядит правильно? Каковы будут вычислительные затраты здесь?

Answer 1

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

• "Hello World" = 0

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

• "XXllo World" = a
• "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.

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

Answer 2

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

Проблема: Вы правильно ищете «достаточно хорошее» решение, так как получить идеальное решение невозможно (я могу показать это в теории информации, но я перейду к геометрии, так как более читабельно). У вас есть 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

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

Для быстрого решения я предлагаю вам использовать расстояние Левенштейна от 3-х струн, описанных ниже быстрая попытка 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/mathematics/geometry/book/978-3-642-00233-5

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

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

Ваши размеры - это произведение элементов вашего алфавита и позиций в строке. Учитывая алфавит («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, чтобы получить сокращенный вектор для слов, даже ранее невидимых.

Answer 6

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

Answer 7

Это ответ на вопрос "с макушки головы".

По сути, это вычисляет расстояние, в котором предложение 2 отличается от предложения 1, как декартово расстояние от предложения 1 (предполагается, что оно находится в начале координат), где расстояния представляют собой сумму минимальной разности Левенштейна между словом в 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];
        }
    }
}

Answer 8

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

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

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