1

現在学習しているF＃をよりよく理解するための演習の一環として、指定された文字列をnグラムに分割する関数を作成しました。
1）自分の関数に関するフィードバックを受け取りたい：これはもっと簡単に、またはもっと効率的に書くことができますか？

2）私の全体的な目標は、n-gramの類似性に基づいて文字列の類似性（0.0 .. 1.0スケール）を返す関数を作成することです。このアプローチは短い文字列の比較に適していますか、またはこの方法を使用して大きな文字列（記事など）を確実に比較できますか？

3）n-gram比較が2つの文字列のコンテキストを無視するという事実を認識しています。私の目標を達成するためにどのような方法を提案しますか？ 

//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 グラムを抽出するために必要なものです。このSeq.groupBy関数は、シーケンス (n グラム) の要素を、同じキーを持つ値を含むグループのシーケンスに収集します。を使用idしてキーを計算します。これは、n グラム自体がキーであることを意味します (したがって、各グループに同じ n グラムが含まれるグループを取得します)。次に、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) 2 つの短い弦の間の距離を比較します。一般的な方法は、単純な動的プログラミングを使用してEdit Distanceを使用することです。記事間の類似度を計算するための最先端の方法は、TFIDF特徴表現を使用することです。実際、上記のコードは用語の頻度をカウントするためのもので、私のデータ マイニング ライブラリから抽出されたものです。

(3) 複雑な NLP メソッドがあります。たとえば、解析ツリーに基づくツリー カーネルで、コンテキスト情報を連携させます。

于 2010-05-25T13:48:47.870 に答える
1

質問 (1) に対する適切な回答があると思います。

質問2）：

n-gram の 2 つの任意のコレクション (大きい方が良い) を比較するには、おそらくコサイン類似度が必要です。これにより、スケーリングを必要とせずに 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 の回答のようなものを実行して 2 つのマップを取得し、1 つだけに存在するキーを削除する必要があります。

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を代わりに使用しています (ビールと自由のように)。精度がどの程度かはわかりませんが、少なくとも英語や関連言語については、最近では POS タグ付けの問題がよく理解されています。

質問 (3):

ほぼ同一の 2 つの文字列を比較する最良の方法は、レーベンシュタイン距離です。それがあなたの場合かどうかはわかりませんが、たとえば 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 に答える