2

iTunes API からアップロードした曲トラックのリストがあります。それらの一部は複製ですが、完全な複製ではありません。たとえば、「All 4 u」と「All for you」、または「Some song」と「some song feat. some other artist」のように言うことができます。

重複を特定できるようにしたい。すべてのペアのレーベンシュタイン距離を計算する最良の方法は? それは過剰に思えます。

私は iOS プログラミング用の Cocoa Touch フレームワークで作業しているので、誰かが大いに役立つライブラリを知っていれば.

4

1 に答える 1

3

レーベンシュタイン距離の計算が過剰であると考えるのはなぜですか? 鉛筆と紙を持ってリストに座っているとしたら、どのアルゴリズムを使用しますか?

とはいえ、レーベンシュタインはおそらく必要ですが、十分ではありません. 文字列を正規化することから始めます。場合によっては、文字列がいくつかの方法で正規化される可能性があり、両方を行う必要があります。正規化は次のようになります。

  • 小文字に変換
  • 先頭の数字とそれに続く句読点 (「1.」、「1 -」など) を取り除きます。
  • 「feat.」以降はとりあえず剥ぎます。または「と」
    • これは、問題セットに関する特別な知識の例です。このような特殊な知識をたくさん使わなければなりません。
    • 「暫定的に」とは、文字列のストリップされたバージョンとストリップされていないバージョンの両方を保持する必要があることを意味します
    • 「偉業」を含むものに注意してください。リミックスの可能性があるため、重複を想定する場合は注意が必要です。もちろん、これはほとんどすべての重複除外の試みに当てはまります。多くの場合、複数のバージョンがあります。
  • 一般的な略語を暫定的に展開します (u=>you、4=>for、2=>two、w/=>with など)。
  • 括弧内を仮に削除
  • 英語の記事 (a、an、the) を取り除きます。最初のパスとして、すべての非常に短い単語 (3 文字以下) を取り除くことさえあるかもしれません。

これをうまく行うのは複雑で、多くの試行錯誤が必要です。私は過去に多くの連絡先の重複排除を行ってきましたが、1 つのアドバイスとして、保守的に始めてください。誤って重複除外をやりすぎてしまうのは非常に簡単です。手動で重複排除したテスト データの大きなリストを作成し、アルゴリズムが変更されるたびにテスト、テスト、テストを繰り返します。確信できないレコードが非常に多くなるため、UI がユーザーに不確かなものを提示できることを確認してください。(これは、手動で行う場合にも当てはまります。人間が入力したタイトルの大きなリストを見て、トラックを聞かずに 100% 重複しているタイトルを教えてください。コンピューターは、この点であなたよりもうまく機能することはありません。 .)

このために公開されているライブラリについては知りません。これは多くの人によって何度も解決されています (「曲名の重複除去」などで検索してください)。しかし、それは一般的に商用ソフトウェアです。

これは巨大な O(n^2) またはそれ以上の問題であるため、もう 1 つアドバイスがあります。バケット化の機会を探します。最初にアーティスト、次にアルバム、次にトラックを一致させることができれば、分割して征服する時間を大幅に短縮できます。

于 2013-03-04T17:18:53.720 に答える