2

検索文字列に共通の最大長の左境界部分文字列を共有するすべてのテキスト結果を返す必要があります。

次を含むテーブル列で「StackOverflow」を検索すると、

"Stack",
"Sta", 
"StackOv", 
"StackOverthrow",
"StackOverSlow",
"StackFlow", 
"Soverflow",
"StackOverCrow",
"StackOverSlow",
etc.

一致する文字が最大数含まれているため、クエリは「StackOverthrow」を返し、一意の結果セットに StackOverSlow と StackOverCrow を返します。現在、最初の文字の LIKE 検索から開始し、何も見つからなくなるまで検索文字列を繰り返して拡張し、最後の良い結果を維持するという非効率的なことを行っています。

すなわち

select names from table where name like 'XX%';


 "S" ->Results
 "St"->Results
 . .
 "StackOver"->Results 
 "StackOverf"-> No results (Last result returning items beginning with StackOver etc  as being the correct answer)

このアプローチが非常に非効率的であることはわかっていますが、この結果を達成するために単一のクエリを提供できる人はいますか? すべての組み合わせを一度に検索して、コード内の最長の結果をフィルタリングできることはわかっていますが、DB の方が優れていると思います。

Edit1: 上記の例はやや単純化されていることに注意してください。DB 内のデータの大部分は 2 ～ 10 文字で、最も一般的な一致の長さは約 3 文字です。テーブルには 100K を超えるレコードがあります。

Edit2: 申し訳ありませんが、複数の正しい結果が存在する可能性があり、結果には削除が必要な重複が含まれている可能性があることを明確にする必要がありました。現在、私の非効率的な方法では、個別の選択は簡単です。

4

3 に答える 3

3

のインデックスを使用するnameと、次のパフォーマンスが非常に高くなるはずです。

SELECT DISTINCT name
FROM   myTable
WHERE  name LIKE CASE
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'S%') THEN '%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'St%') THEN 'S%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'Sta%') THEN 'St%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'Stac%') THEN 'Sta%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'Stack%') THEN 'Stac%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackO%') THEN 'Stack%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOv%') THEN 'StackO%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOve%') THEN 'StackOv%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOver%') THEN 'StackOve%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOverf%') THEN 'StackOver%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOverfl%') THEN 'StackOverf%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOverflo%') THEN 'StackOverfl%'
  WHEN NOT EXISTS(SELECT * FROM myTable WHERE name LIKE 'StackOverflow%') THEN 'StackOverflo%'
  ELSE 'StackOverflow%'
END

sqlfiddleで参照してください。

于 2012-12-03T16:25:59.230 に答える
1

レーベンシュタイン距離ストアド関数を作成した後、クエリを実行できます。これにより、最適な結果が得られる可能性があります。

これは私のコードではありません。私はここからこれを手に入れました。sqlfiddle でうまくテストされているようです。

CREATE FUNCTION levenshtein( s1 VARCHAR(255), s2 VARCHAR(255) )
  RETURNS INT
  DETERMINISTIC
  BEGIN
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT;
    DECLARE s1_char CHAR;
    -- max strlen=255
    DECLARE cv0, cv1 VARBINARY(256);
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0;
    IF s1 = s2 THEN
      RETURN 0;
    ELSEIF s1_len = 0 THEN
      RETURN s2_len;
    ELSEIF s2_len = 0 THEN
      RETURN s1_len;
    ELSE
      WHILE j <= s2_len DO
        SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1;
      END WHILE;
      WHILE i <= s1_len DO
        SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1;
        WHILE j <= s2_len DO
          SET c = c + 1;
          IF s1_char = SUBSTRING(s2, j, 1) THEN 
            SET cost = 0; ELSE SET cost = 1;
          END IF;
          SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost;
          IF c > c_temp THEN SET c = c_temp; END IF;
            SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1;
            IF c > c_temp THEN 
              SET c = c_temp; 
            END IF;
            SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1;
        END WHILE;
        SET cv1 = cv0, i = i + 1;
      END WHILE;
    END IF;
    RETURN c;
  END;

クエリは次のようになります。

SELECT names, levenshtein(`names`, 'StackOverflow') as dist
FROM mytable
ORDER BY dist;

sqlfiddleでこれがどのように見えるかを次に示します。

結果は次のようになります。最小距離が最も近い一致です。

NAMES           DIST
StackOverthrow  3
StackFlow       4
Soverflow       4
StackOv         6
Stack           8
Sta             10
于 2012-12-03T16:51:52.000 に答える
0

最初に最小のものを見る理由がわかりません。私は逆にそれを行います...最初に最長の正確な一致を試み、見つからない場合は、見つかるまで一度に1文字ずつ逆方向に作業します。

于 2012-12-03T16:13:31.003 に答える