データベースに格納されている整数のリストから最も近いセットを見つける

Question

データベーステーブルに格納されている整数のうち最も近いか同じセットを探したいと思います。 格納されるリストの長さは0..10から可変です。要素の順序は重要です。例えば

：

1:[1234, 2345, 5463, 1235] 
2:[2355, 5463, 1235] 
3:[123, 1234, 1235, 5463, 3443] 

私のような新しいセットがある場合：[1235, 5463]を、私は、最寄りまたはマッチングセットを見つけるしたいと思います。この場合3:[123, 1234, 1235, 5463, 3443]。

セットはデータベースに格納されているので、リストをハッシュ値に変換し、指定されたセットから計算されたハッシュに従ってソートします。

私は最初のレコードで最も適切な結果を見つけることができれば、それはperferctである必要はありません。

この問題を解決するには、どのような方法が最適ですか？

または他の適切な解決策があります。

Answer 1

あなたが本当に "最長共通部分文字列"（LCS）を意味していたと仮定すると、ハッシングはあなたを助けません - 実際にはデータベースの各要素でクエリのLCSを計算する必要がありますあなたが言及したように、上のいくつかのもの）。

これを行う最善の方法は、動的プログラミングです。その詳細については、wikipediaを参照してください。