問題タブ [edit-distance]

問題: いくつかの R パッケージは、2 つの文字列の類似度を計算するためのレーベンシュタイン距離の実装を特徴としています。計算された距離は、たとえば、レーベンシュタイン距離を関連する最長の文字列の長さで割るか、2 つの文字列の長さの平均で割ることによって、文字列の長さに対して簡単に正規化できます。ただし、言語学の一部のアプリケーション (例: 弁証法や受容多言語研究) では、生のレーベンシュタイン距離を最長の最小コスト アラインメントの長さで正規化することをお勧めします (Heeringa, 2004: 130-132)。これにより、知覚言語の観点からより意味のある距離測定が生成される傾向があります。

例: ドイツ語の文字列 "tsYklUs" (Zyklus = サイクル) は、2 つの挿入 (I) と 2 つの置換 (S) を持つ 7 スロット アラインメントで、スウェーデン語の同族語 "sYkEl" (cyckel = (bi)cycle) に変換できます。変換コストの合計は 4 です。正規化されたレーベンシュタイン距離: 4/7

(ア)

また、3 つの挿入 (I) と 1 つの削除 (D) を含む 8 スロット アラインメントで文字列を変換することも可能で、総アラインメント コストは 4 です。正規化されたレーベンシュタイン距離: 4/8

(ロ)

後者のアラインメントは、[E] および [U] 母音ではなく、[l] 音素を相互にアラインするため、言語的にはより意味があります。

質問: 適切な文字列の長さではなく、最長の最小コスト アラインメントのためにレーベンシュタイン距離を正規化できるようにする R 関数を知っている人はいますか? ご意見ありがとうございます。

参照: WJ Heeringa (2004)、レーベンシュタイン距離を使用した方言発音の違いの測定。博士論文、フローニンゲン大学。http://www.let.rug.nl/~heeringa/dialectology/thesis/

編集 - 解決策: 解決策を見つけたと思います。このadist関数はアラインメントを返すことができ、デフォルトで最長の低コスト アラインメントになるようです。上記の例を取り上げると、sykelからtsyklusに関連付けられたアラインメントは次のとおりです。

Heeringa (2004) が推奨する長さ正規化距離を計算するには、控えめな関数を記述できます。

上記の例では、これは次を返します。

この関数は、Heeringa (2004: 131) の例の正しい正規化された距離も返します。

複数の文字列のペアを比較するには:

C＃で実装されている2つの隣接する文字が転置される場合もサポートする、レーベンシュタイン編集距離を計算するためのアルゴリズムを探しています。

たとえば、「animals」と「ainmals」という単語：「n」と「i」の文字を切り替えると、2つの置換としてスコアが付けられず、距離が長くなりますが、代わりに2つの文字の転置としてスコアが付けられます。はるかに短い距離-

検索でこれまでに到達したもの

• Lichtenstein距離を計算 していますが、置換は含まれていません
• この質問

私の質問は、有効な単語を介して1つの単語を別の単語に変換するアルゴリズムに似ています

しかし、とは大きな違いです。「JAMES」という固定語と、i/pとしてさまざまな辞書があります。もちろん、今は辞書を前処理することはできません。

そのため、さまざまな辞書を入力として「JAMES」から「JOHNY」を処理するための最小コストを見つける必要があります。

とにかく、実行時に最小数の編集距離計算を実行する必要があるように、「JAMES」という単語を前処理することはできますか？あなたたちは何を提案しますか？

2 つの文字列の比較に基づいて類似性スコアを割り当てようとしています。Rにも同じ機能がありますか.SPEDISの名前でSASにそのような機能があることを知っています. Rにそのような機能があるかどうか教えてください。

編集距離のアルゴリズムは、2つの文字列間の距離の尺度を提供します。

質問：実際に同じである2人の異なる人物の名前を検出するために、これらの測定値のどれが最も関連性がありますか？（スペルミスのために異なります）。秘訣は、誤検知を最小限に抑える必要があるということです。例：

オバマオバマ=>おそらくマージする必要があります

オバマイバマ=>マージしないでください。

これは単純すぎる例です。この問題をより詳細に解決したプログラマーやコンピューター科学者はいますか？

これは理論上の質問なので、疑似コードを使用します。

別のリストに変換する必要があるオブジェクトのリストがあります。

私はレーベンシュタイン アルゴリズムを実装しました。これは問題なく動作しますが、新しいオブジェクトを作成するのではなく、オブジェクトを保持する必要があります。私はそれを強引に行うことができますが、これを行うには O(n*m) 以外の方法を見つけたいと思います。

[obj1,obj2,obj3] -> [obj1,obj4,obj5,obj2,obj6,obj3]

obj1、obj2、obj3 は同じオブジェクトである必要があり、残りは新しく作成されたオブジェクトです。

これに適したアルゴリズムを知っている人はいますか？

UTF-8、UTF-16、およびUTF-32 Unicode文字標準を使用して、50を超える国際言語でファジーマッチングを実行するシステムを開発しています。これまでのところ、レーベンシュタイン距離を使用して、ドイツ語のUnicode拡張文字の単語のスペルミスを検出することができました。

このシステムを拡張して、Unicodeで表される北京語の表意文字を処理できるようにします。類似の漢字間のレーベンシュタイン距離の計算をどのように実行しますか？

「AGTE」という文字列の2 つのグループAとBがあり、これらを比較して統計的に類似しているかどうかを確認する方法を見つけたいと考えています。最初のグループ A は実際の観測で、B は予測です。各グループには約 400 人がいます。

また、実際にプレゼンテーションを目的として、これらを何らかの方法で視覚化できるようにしたいと考えています。どうすればそれができるようになるのか、何かアイデアはありますか?

レーベンシュタイン編集距離を実際に計算する必要はないことに注意してください。1かどうかを確認してください。

メソッドのシグネチャは次のようになります。

例：1。「abc」と「ab」はtrueを返します2.「abc」と「aebc」はtrueを返します3.「abc」と「a」はfalseを返します

再帰的な承認を試みましたが、効率的ではありません。

更新：友人から回答を得ました：

私たち全員がGoogleで見てきましたが、クエリを入力してタイプミスをすると、Googleはクエリのより適切なバージョンを提案します（これはほとんどの場合正しいです）。今、彼らはそれをどのように行うのですか？私が考えることができる1つの可能な方法は、指定された文字列から編集距離1にある他のすべての文字列を見つけ、それらのいずれかがより高い値の'searched`属性を持つ文字列を返す場合です（バックエンドDBからのものである可能性があります。インデックス付けされた各クエリ用語には、指定された文字列よりもその用語がクエリで出現する頻度に基づいて重みが関連付けられている場合、その文字列が提案されます。何も見つからない場合は、編集距離が2の文字列が検索され、たとえば5になるまで、SEはこの文字列がユーザーが探している文字列である可能性があると判断し、対応する検索結果を返します。

これで、特定の文字列から特定の編集距離にある文字列を見つけることができますか？それはこのプロセスにとってどれほど効率的でしょうか？これを行うためのクールなアルゴリズムはありますか？