用于字符串相似性比较的N-gram分割函数

Question

作为更好地理解我目前正在学习的F#的一部分,我编写了将给定字符串拆分为n-gram的函数.
1)我想收到有关我的功能的反馈:这可以更简单或更有效地编写吗？

2)我的总体目标是编写基于n-gram相似性返回字符串相似度(在0.0 ... 1.0范围内)的函数; 这种方法是否适用于短字符串比较,或者这种方法可以可靠地用于比较大字符串(例如文章).

3)我知道n-gram比较忽略了两个字符串的上下文.你建议用什么方法来实现我的目标？

//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)
                                        ) 

Answer 1

我对评估字符串的相似性知之甚少,所以我不能就第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-gram所需要的.该Seq.groupBy函数将序列元素(n-gram)收集到包含具有相同键的值的组序列中.我们id用来计算密钥,这意味着n-gram本身就是关键(因此我们得到组,每组包含相同的n-gram).然后我们只需将n-gram转换为字符串并计算组中元素的数量.

或者,您可以将整个函数编写为单个处理管道,如下所示:

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