7

これは、より複雑なフォローアップの質問です。連続した値を検索する効率的な方法

各製品には、多くのセグメント行（数千）を含めることができます。各セグメントには、各製品（1、2、3、4、5など）の1から始まる位置列と、（323.113、5423.231、873.42、422.64、763.1など）などの任意の値を含むことができる値列があります。 ）。データは読み取り専用です。

製品を曲として、セグメントを曲の音符のセットとして考えると役立つ場合があります。

曲のスニペットなど、連続するセグメントのサブセットを前提として、製品に一致する可能性のあるものを特定したいと思います。ただし、測定値にエラーが発生する可能性があるため、サブセット内のセグメントがデータベース内のセグメントと正確に一致しない場合があります。

測定したセグメントのサブセットに最も近い製品のセグメントを見つけることで、製品候補を特定するにはどうすればよいですか？また、データベースはこのタイプのデータに最適なメディアですか？

-

これが、私がこの問題にどのように取り組んでいたかについてのいくつかの考えです。これらを正確な要件と見なさないでください。私は、これを可能な限り最高に機能させるために、あらゆる種類のアルゴリズムを受け入れています。近さを判断するには、複数のしきい値変数が必要だと考えていました。1つの可能性は、近接しきい値と一致しきい値を実装することです。

たとえば、次の値が与えられます。

Product A contains these segments: 11,21,13,13,15.
Measurement 1 has captured: 20,14,14,15.
Measurement 2 has captured: 11,21,78,13.
Measurement 3 has captured: 15,13,21,13,11.

近接しきい値により、測定されたセグメントが実際のセグメントより1上または下になる場合、測定1は製品Aと一致する可能性があります。これは、多くのセグメントが正確に一致しない場合でも、実際の値に対して近接しきい値内にあるためです。

一致しきい値が3以上の一致の測定に許可されている場合、測定2は製品Aを返す可能性があります。これは、セグメントの1つ（78）が近接しきい値をはるかに超えているにもかかわらず、正しい順序で3つのセグメントに一致しているため、一致しきい値。

測定されたすべてのセグメントは実際のセグメントに存在しますが、近接または一致のしきい値内にないため、測定3は製品Aと一致しません。

更新：回答の1つで、最も厳密に一致することの意味を定義するように求められました。どう答えたらいいのかよくわかりませんが、歌のアナロジーを続けて説明しようと思います。セグメントが録音された曲の最大周波数を表すとしましょう。同じ曲をもう一度録音すると似たようなものになりますが、バックグラウンドノイズや録音機器のその他の制限により、周波数の一部が一致し、一部が近くなり、一部がかなり離れます。このシナリオでは、ある録音が別の録音と「一致」するタイミングをどのように定義しますか？これは、この問題で使用するために私が探しているのと同じ種類のマッチングロジックです。

4

4 に答える 4

3

あなたが投稿した情報から、これはエドモンドの花対完全一致アルゴリズムで解決することができます。関数を最小化または最大化することができ、それは常に最適なものを見つけます。たぶん、2つのループを持つブルートフォースソリューションを使用できます。エドモンドのマッチングアルゴリズムに関するウィキペディア：http：//en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm

于 2011-11-10T14:08:31.420 に答える
2

「最も近い」の定義を考え出す必要があります。ここの誰もがデータのビジネス要件や複雑さを知ることはないので、ここの誰もがそれをどのように助けることができるのかわかりません。あなたの2つの方法はどちらも合理的に聞こえますが、実際にそうであるかどうかはわかりません。

データベースがこの種のデータの正しい媒体であるかどうかについては、データベースはおそらくデータの完璧な媒体であると言えますが、データを処理するための正しい媒体ではないようです。それが可能かどうかは、「最も密接に一致する」ものを構成する最終的な解決策に依存します。

簡単に言うと、SSISには、データを処理するためのあいまい一致機能が組み込まれています。私はそれをいじっただけですが、それは数年前のことなので、あなたがしていることにうまくいくかどうかはわかりません。

于 2011-11-07T20:48:35.097 に答える
1

位置ごとに各セグメント位置に対して測定値を照合し、各位置の差を計算するアプローチをとることができますか。次に、測定値を1つの位置に沿ってスライドさせ、差を計算します。次に、どのスライド位置が最も低い差を記録したかを見つけます。すべての製品に対してこれを行うと、測定値が最も近い製品と一致する製品がわかります。

テストテーブルとデータ：

CREATE TABLE [dbo].[Segment]
(
    [ProductId] INT,
    [Position] INT,
    [Value] INT
)

INSERT  [dbo].[Segment]
VALUES  (1, 1, 300),
        (1, 2, 5000),
        (1, 3, 900),
        (1, 4, 400),
        (1, 5, 800),

        (2, 1, 400),
        (2, 2, 6000),
        (2, 3, 1000),
        (2, 4, 500),
        (2, 5, 900),

        (3, 1, 400),
        (3, 2, 5400),
        (3, 3, 900),
        (3, 4, 400),
        (3, 5, 900)

CREATE TABLE #Measurement
(
    [Position] INT,
    [Value] INT
)

INSERT  #Measurement
VALUES  (1, 5400),
        (2, 900),
        (3, 400)

ご覧のとおり、測定値は3番目の製品（のサブセット）と正確に一致しています。

一部のヘルパー：

CREATE TABLE #ProductSegmentCount
(
    [ProductId] INT,
    [SegmentCount] INT
)

INSERT #ProductSegmentCount
SELECT [ProductId], MAX([Position])
FROM [dbo].[Segment]
GROUP BY [ProductId]

DECLARE @MeasurementSegmentCount INT = (SELECT MAX([Position]) FROM #Measurement)

最も近い一致順に並べられた製品を表示する再帰共通テーブル式：

;WITH [cteRecursive] AS
(
    SELECT  s.[ProductId],
            0 AS [RecursionId],
            m.[Position] AS [MeasurementPosition],
            s.[Position] AS [SegmentPosition],
            ABS(m.[Value] - s.[Value]) AS [Difference]
    FROM #Measurement m
    INNER JOIN [dbo].[Segment] s 
        ON m.[Position] = s.[Position]
    UNION ALL
    SELECT s.[ProductId],
            [RecursionId] + 1 AS [RecursionId],
            m.[Position],
            s.[Position],
            ABS(m.[Value] - s.[Value]) AS [Difference]
    FROM [cteRecursive] r
    INNER JOIN #Measurement m
        ON m.[Position] = r.[MeasurementPosition]
    INNER JOIN [dbo].[Segment] s 
        ON r.[ProductId] = s.[ProductId]
        AND m.[Position] + (r.[RecursionId]) = s.[Position]
    INNER JOIN #ProductSegmentCount psc
        ON s.[ProductId] = psc.[ProductId]
    WHERE [RecursionId] <= ABS(@MeasurementSegmentCount - psc.[SegmentCount])
)-- select * from [cteRecursive] where [ProductId] = 3 order by RecursionId, SegmentPosition
, [cteDifferences] AS
(
    SELECT [ProductId], [RecursionId], SUM([Difference]) AS [Difference]
    FROM [cteRecursive]
    GROUP BY [ProductId], [RecursionId]
)-- select * from [cteDifferences]
SELECT [ProductId], MIN([Difference]) AS [Difference]
FROM [cteDifferences] 
GROUP BY [ProductId]
ORDER BY MIN([Difference])
OPTION (MAXRECURSION 0)
于 2011-11-10T17:33:15.603 に答える
1

文字通り曲の例をとる場合、1つのアプローチは、入力をビットベクトルフィンガープリントに要約し、データベースでそのフィンガープリントを完全一致として検索することです。入力からいくつかの指紋を抽出したり、指紋から1つまたはビットエラーだけ離れているすべてのビットベクトルを試したりすることで、適切な一致を見つける可能性を高めることができます。

ACMデジタルライブラリにアクセスできる場合は、この種のアプローチの説明を「The Shazam MusicRecognitionservice」（acm = 1321038137_73cd62cf2b16cd73ca9070e7d5ea0744 "> http://delivery.acm.org/10.1145/1150000/1145312/）で読むことができます。 p44-wang.pdf？ip = 94.195.253.182＆acc = ACTIVE％20SERVICE＆CFID = 53180383＆CFTOKEN = 41480065＆acm =1321038137_73cd62cf2b16cd73ca9070e7d5ea0744。http://www.music.mcgill.ca/~alastair/621/porter11にも情報があります。 .pdf。

あなたが説明する入力フォーマットは、 http：//en.wikipedia.org/wiki/Locality_sensitive_hashingで説明されているランダム射影法で何かを行うことができるかもしれないことを示唆しています。

2番目の質問に答えるには、位置が正確に何に対応するかに応じて、ビットまたは文字で構成されるフィンガープリントをハッシュするために数値を煮詰めて、ApacheLuceneなどのテキスト検索データベースに保存することを検討してください。

于 2011-11-12T11:50:33.830 に答える