Функция разбиения N-граммы для сравнения сходства строк - PullRequest
Новая
       19

Функция разбиения N-граммы для сравнения сходства строк

1 голос
/ 25 мая 2010

В качестве части упражнения, чтобы лучше понять F #, который я сейчас изучаю, я написал функцию для разбить данную строку на n-грамм.
1) Я хотел бы получить отзыв о моей функции: это можно написать проще или эффективнее?

2) Моя общая цель - написать функцию, которая возвращает сходство строк (по шкале 0,0 .. 1,0) на основе сходства n-грамм; Хорошо ли подходит этот подход для сравнения коротких строк или этот метод можно надежно использовать для сравнения больших строк (например, статей).

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

//s:string - target string to split into n-grams
//n:int - n-gram size to split string into
let ngram_split (s:string, n:int) =
    let ngram_count = s.Length - (s.Length % n)
    let ngram_list = List.init ngram_count (fun i ->
        if( i + n >= s.Length ) then
        s.Substring(i,s.Length - i) + String.init ((i + n) - s.Length)
            (fun i -> "#")
        else
            s.Substring(i,n)
    )
    let ngram_array_unique = ngram_list
                            |> Seq.ofList
                            |> Seq.distinct
                            |> Array.ofSeq

//produce tuples of ngrams (ngram string,how much occurrences in original string)

    Seq.init ngram_array_unique.Length (fun i -> (ngram_array_unique.[i],
        ngram_list |> List.filter(fun item -> item = ngram_array_unique.[i])
                                   |> List.length)
                                        )

Ответы [ 4 ]

5 голосов
/ 25 мая 2010

Я не очень разбираюсь в оценке сходства строк, поэтому не могу дать вам много отзывов относительно пунктов 2 и 3. Однако вот несколько советов, которые могут помочь сделать вашу реализацию проще.

Многие из необходимых вам операций уже доступны в некоторых функциях библиотеки F # для работы с последовательностями (списками, массивами и т. Д.). Строки также являются последовательностями (из символов), поэтому вы можете написать следующее: 

open System

let ngramSplit n (s:string) = 
  let ngrams = Seq.windowed n s
  let grouped = Seq.groupBy id ngrams
  Seq.map (fun (ngram, occurrences) -> 
    String(ngram), Seq.length occurrences) grouped

Функция Seq.windowed реализует скользящее окно, которое является именно тем, что вам нужно для извлечения n-граммов вашей строки. Функция Seq.groupBy собирает элементы последовательности (n-граммы) в последовательность групп, которые содержат значения с одинаковым ключом. Мы используем id для вычисления ключа, что означает, что n-грамм сам является ключом (и поэтому мы получаем группы, где каждая группа содержит одинаковые n-граммы). Затем мы просто конвертируем n-грамм в строку и подсчитываем количество элементов в группе.

В качестве альтернативы, вы можете написать всю функцию как один конвейер обработки, например: 

let ngramSplit n (s:string) = 
  s |> Seq.windowed n
    |> Seq.groupBy id 
    |> Seq.map (fun (ngram, occurrences) -> 
         String(ngram), Seq.length occurrences)
1 голос
/ 25 мая 2010

Я думаю, у вас есть несколько хороших ответов на вопрос (1).

Вопрос (2):

Возможно, вы хотите, чтобы косинусное сходство сравнивалось с двумя произвольными наборами n-грамм (чем больше, тем лучше). Это дает вам диапазон от 0,0 до 1,0 без необходимости масштабирования. Страница Википедии дает уравнение , а перевод F # довольно прост: 

let cos a b = 
  let dot = Seq.sum (Seq.map2 ( * ) a b)
  let magnitude v = Math.Sqrt (Seq.sum (Seq.map2 ( * ) v v))
  dot / (magnitude a * magnitude b)

Для ввода вам нужно выполнить что-то вроде ответа Томаса, чтобы получить две карты, а затем удалить ключи, которые существуют только в одной: 

let values map = map |> Map.toSeq |> Seq.map snd
let desparse map1 map2 = Map.filter (fun k _ -> Map.containsKey k map2) map1
let distance textA textB =
  let a = ngramSplit 3 textA |> Map.ofSeq
  let b = ngramSplit 3 textB |> Map.ofSeq
  let aValues = desparse a b |> values
  let bValues = desparse b a |> values
  cos aValues bValues

С символьными n-граммами я не знаю, насколько хорошими будут ваши результаты. Это зависит от того, какие особенности текста вас интересуют. Я занимаюсь обработкой на естественном языке, поэтому обычно мой первый шаг - это пометка части речи. Затем я сравниваю н-граммы частей речи. Я использую T'n'T для этого, но у него есть странные проблемы с лицензированием. Некоторые из моих коллег вместо этого используют ACOPOST , бесплатную альтернативу (как в случае пива и свободы). Я не знаю, насколько точна точность, но POS-теги - это хорошо понятная проблема в наши дни, по крайней мере, для английского языка и родственных языков.

Вопрос (3):

Лучший способ сравнить две почти одинаковые строки - это Расстояние Левенштейна . Я не знаю, так ли это здесь, хотя вы можете ослабить допущения несколькими способами, например, для сравнения цепочек ДНК.

Стандартной книгой по этому предмету является книга Санькоффа и Крускала "Деформации времени, струнные правки и маромолекулы" Он довольно старый (1983 г.), но дает хорошие примеры того, как адаптировать базовый алгоритм к ряду приложений.

1 голос
/ 25 мая 2010

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

Шаблон MapReduce очень подходит для вашей задачи подсчета частоты:

  1. получить строку, испустить (слово, 1) пары

  2. сделать группировку слов и сложить все подсчеты вместе.

    let wordCntReducer (wseq: seq<int*int>) =

       wseq 
   |> Seq.groupBy (fun (id,cnt) -> id) 
   |> Seq.map (fun (id, idseq) -> 
            (id, idseq |> Seq.sumBy(fun (id,cnt) -> cnt)))
(* test: wordCntReducer [1,1; 2,1; 1,1; 2,1; 2,2;] *)

Вам также необходимо поддерживать карту <word,int> во время построения ngram для набора строк. Поскольку гораздо более эффективно обрабатывать целые числа, а не строки во время последующей обработки.

(2) для сравнения расстояния между двумя короткими строками. Обычной практикой является использование Edit Distance с использованием простого динамического программирования. Чтобы вычислить сходство между статьями, современный метод должен использовать TFIDF представление функции. На самом деле приведенный выше код предназначен для подсчета частот, взятого из моей библиотеки интеллектуального анализа данных.

(3) Существуют сложные методы НЛП, например, Ядра дерева, основанные на дереве разбора, для взаимодействия с контекстной информацией в.

0 голосов
/ 25 мая 2010

Вопрос 3:

Мой справочник - Вычисление шаблонов в строках Биллом Смитом

...