2

私の質問は、2 つの文字列を比較する最速の方法 (品質も重要ですが、それほど重要ではありません) は何ですか?

2 つの文字列を比較する最も効率的な方法を探しています。私が比較している文字列の中には、5000 文字を超えるものもあります。約 80 個の文字列のリストと約 200 個の文字列の別のリストを比較しています。私がそれをスレッド化していても、それは永遠にかかります。StringUtils.getLevenshteinDistance(String s, String t)Apache Commonsのメソッドを使用しています。私の方法は次のとおりです。これを行うより良い方法はありますか？

private void compareMe() {
  List<String> compareStrings = MainController.getInstance().getCompareStrings();
  for (String compare : compareStrings) {
    int levenshteinDistance = StringUtils.getLevenshteinDistance(me, compare);
    if (bestScore > levenshteinDistance
          && levenshteinDistance > -1) {
      bestScore = levenshteinDistance; //global variable
      bestString = compare; //global variable
    }
  }
}

良いスコアを持つべき 2 つの文字列のサンプルを次に示します。

文字列 1:

SELECT 
CORP_VENDOR_NAME as "Corporate Vendor Name",
CORP_VENDOR_REF_ID as "Reference ID",
MERCHANT_ID as "Merchant ID",
VENDOR_CITY as "City",
VENDOR_STATE as "State",
VENDOR_ZIP as "Zip",
VENDOR_COUNTRY as "Country",
REMIT_VENDOR_NAME as "Remit Name",
REMIT_VENDOR_REF_ID as " Remit Reference ID",
VENDOR_PRI_UNSPSC_CODE as "Primary UNSPSC"
FROM DSS_FIN_USER.ACQ_VENDOR_DIM
WHERE VENDOR_REFERENCE_ID in 
(SELECT distinct CORP_VENDOR_REF_ID
FROM DSS_FIN_USER.ACQ_VENDOR_DIM
WHERE CORP_VENDOR_REF_ID = '${request.corp_vendor_id};')

文字列 2:

SELECT 
CORP_VENDOR_NAME as "Corporate Vendor Name",
CORP_VENDOR_REF_ID as "Reference ID",
MERCHANT_ID as "Merchant ID",
VENDOR_CITY as "City",
VENDOR_STATE as "State",
VENDOR_ZIP as "Zip",
VENDOR_COUNTRY as "Country",
REMIT_VENDOR_NAME as "Remit Name",
REMIT_VENDOR_REF_ID as " Remit Reference ID",
VENDOR_PRI_UNSPSC_CODE as "Primary UNSPSC"
FROM DSS_FIN_USER.ACQ_VENDOR_DIM
WHERE VENDOR_REFERENCE_ID in 
(SELECT distinct CORP_VENDOR_REF_ID
FROM DSS_FIN_USER.ACQ_VENDOR_DIM
WHERE CORP_VENDOR_REF_ID = 'ACQ-169013')

'${request.corp_vendor_id};'唯一の違いは、文字列の末尾にあることに気付くでしょう。これにより、メソッド26からのスコアが得られます。LevenshteinDistance

4

1 に答える 1

2

一部の計算をまったく回避するために、比較ロジックで可能なショートカットについて考える必要があります。したがって、レーベンシュタイン距離を全体的に最小化したい場合、文字列サイズの差が現在の最適なレーベンシュタイン距離よりも大きい場合は、計算する必要さえありません。

たとえば、現在の最適なレーベンシュタイン距離が 50 の場合、サイズが 100 と 180 の 2 つの文字列の比較を避けることができます。これは、それらのレーベンシュタイン距離が少なくとも 80 であるためです。

于 2012-05-24T19:51:52.057 に答える