1

作为练习的一部分，为了更好地理解我目前正在学习的 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)
                                        )
4

4 回答 4

5

我对评估字符串的相似性知之甚少，因此无法就第 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)
于 2010-05-25T13:42:08.117 回答
2

你的代码对我来说看起来不错。由于经常使用 ngram 提取和相似性比较。您应该在这里考虑一些效率问题。

MapReduce 模式非常适合您的频率计数问题：

  1. 得到一个字符串，发出 (word, 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)比较两个短字符串之间的距离。一种常见的做法是使用简单的动态规划来使用编辑距离。为了计算文章之间的相似度，最先进的方法是使用TFIDF特征表示。实际上，上面的代码是从我的数据挖掘库中提取的词频计数。

(3) 有复杂的 NLP 方法，例如基于解析树的树核，以在其中协同上下文信息。

于 2010-05-25T13:48:47.870 回答
1

我认为您对问题（1）有一些很好的答案。

问题2）：

您可能希望余弦相似度来比较两个任意的 n-gram 集合（越大越好）。这为您提供了 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)

对于输入，您需要运行类似 Tomas 的答案以获取两张地图，然后删除仅存在于一张地图中的键：

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-gram，我不知道你的结果会有多好。这取决于您对文本的哪种特征感兴趣。我做自然语言处理，所以通常我的第一步是词性标记。然后我比较了 n-gram 的词性。我为此使用 T'n'T，但它有奇怪的许可问题。我的一些同事改用ACOPOST，这是一种免费的替代品（如啤酒和自由）。我不知道准确度有多好，但词性标注现在是一个众所周知的问题，至少对于英语和相关语言来说是这样。

问题（3）：

比较两个几乎相同的字符串的最佳方法是Levenshtein distance。我不知道这是否是您的情况，尽管您可以通过多种方式放松假设，例如比较 DNA 字符串。

关于这个主题的标准书籍是 Sankoff 和 Kruskal 的“Time Warps, String Edits, and Maromolecules”。它相当古老（1983 年），但给出了如何将基本算法应用于许多应用程序的很好的例子。

于 2010-05-25T14:07:30.430 回答
0

问题 3：

我的参考书是Bill Smyth 的《Computing Patterns in Strings 》

于 2010-05-25T18:05:33.270 回答