3

こんにちは、ご覧いただきありがとうございます。

バックグラウンド

約 3400 文字のエンコードされたデータの文字列を含む 1900 個のノードを含む XML ファイルがあります。

私が開発しているアプリケーションのユースケースの一部として、実行時に「ベンチマーク」文字列を取得し、XML ファイルから最も近い一致を見つけることができる必要があります。

XML はアプリとは密接な関係がなく、今後は SQL を使用する可能性があることに注意してください。ただし、今日は、データを保存して概念を証明するための簡単な場所が必要でした。

.NET 4.0、C#、フォーム アプリ、LINQ などを使用しています。

質問

最も近い一致を見つけるにはどうすればよいですか? ハミング？レーベンシュタイン？オンラインにはたくさんのコード サンプルがありますが、ほとんどは小さな文字列の比較 ("ant" と "aunt") または完全一致を目的としています。完全に一致することはめったにありません。最も近い一致が必要です。

前もって感謝します！

マット

4

1 に答える 1

1

あなたは、Levenhstein の Edit Distanceを使用し、文字列の長さが約 3400 文字であると述べました。

私は簡単に試してみました.Levenhsteinの編集距離の動的プログラミングバージョンを使用すると、非常に高速で問題が発生しないようです.

これは私がしました：

        final StringBuilder sb1 = new StringBuilder();
        final StringBuilder sb2 = new StringBuilder();
        final Random r = new Random(42);
        final int n = 3400;
        for (int i = 0; i < n; i++) {
            sb1.append( (char) ('a' + r.nextInt(26)) );
            sb2.append( (char) ('a' + r.nextInt(26)) );
        }
        final long t0 = System.currentTimeMillis();
        System.out.println("LED: " + getLevenshteinDistance(sb1.toString(), sb2.toString()) );
        final long te = System.currentTimeMillis() - t0;
        System.out.println("Took: " + te + " ms");

そして、2006 年くらいから Core 2 Duo で 215 ミリ秒で距離を見つけています。

それはあなたのために働くでしょうか？

(ちなみに、ここにある DP LED 実装のコードを貼り付けることができるかどうかわからないので、インターネットで 1 つの Java 実装を検索する必要があります)

于 2012-01-08T19:15:02.717 に答える