Challenge 7 を試してくれた人々に感謝します。 うまくいけば、機会がなかったとしても、議論に従ってきたことでしょう。 この課題をどのように解決できますか? 概念的には、最も単純なアプローチでは、1 文字の重複、次に 2 文字の重複、3 文字というように、重複がなくなるまで 1 文字ずつ増やしていきます。 指定された長さの可能性のあるすべての文字列を素朴にチェックすると、部分文字列の長さに応じてますます時間がかかります。 約 30K 文字の長さの Covid-19 ゲノムの場合、7 文字の部分文字列の重複が 4 つしかないことが保証されていますが、 7 = 16,384 の一意の組み合わせで、6889 しか発生しません (42%)。 また、部分文字列が長くなるにつれて可能な重複の量が急速に増加するため、重複の数は減少します。 このアプローチが機能するには、重複を識別するための効率的な方法を見つける必要があります。 この問題に取り組む他の方法を検討した後、これに戻ります。
すべての重複を見つけることを心配することなく、最長の重複を見つけることに集中しましょう。 簡単な方法は、最初の文字で部分文字列を開始し、7 文字の重複が存在する必要があるためです。 次に、重複がなくなるまで一度に 1 文字ずつ成長させます。 次の文字と、より長い重複部分文字列に移動します。 重複が不可能なほど検索文字列の末尾に近づくまで、これを続けます。 Covid-19 ゲノムでは、8 文字の部分文字列アタアグ最初の文字から構築できます。 2文字目に移動、11文字の文字列たぁあぐっった位置 2 を開始すると、位置 20063 に重複があります。 3 番目の位置から始まる 11 文字以上の重複がないため、4 番目の位置に移動します。 等々。 以下のコードは、最長の重複文字列を見つけるのに約 5 秒かかります。あ秒。 以下のコードでは、既に見つかった最長の部分文字列と同じ長さの部分文字列の重複が存在する場合、その間終了する前に少なくとももう一度繰り返します。 これらの状況では次のレン1 減らす必要があります。
findLongestDupe = Function({inString,charSet},{parts,nextLen,nextPos=1,longestDupes={""}},
parts = Items(inString,"");
nextLen = Floor(Log(Length(inString))/Log(N Items(charSet)));
While(nextPos <= Length(inString)-nextLen+1,
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
While(Contains(inString,nextWord,nextPos+1),
nextLen++;
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
);
nextPos++;
If(Length(nextWord)>Length(longestDupes[1]),
nextLen--; //nextLen will be one more than longest length when Pat Match fails
nextWord = Concat Items(parts[nextPos::(nextPos+nextLen-1)],"");
If(Length(nextWord)==Length(longestDupes[1])+1,
Insert Into(longestDupes,nextWord),
longestDupes = Eval List({nextWord})
);
);
nextChar++;
);
longestDupes;
);
と同様に@Craige_Hales前回のブログ記事に掲載したコードですが、パターンマッチングを使って上記のアプローチを実装してみました。 驚いたことに、結果が出るまでに 5 ～ 6 倍の時間がかかりました。 正確な理由はわかりませんが、私の予感はそうです（前回の図のように）含む部分文字列の重複があまり頻繁に発生しない場合は、はるかに高速です。
JMP に組み込まれている重複検索機能を利用することで、処理を高速化できます。まとめテーブルプラットフォーム。 このアプローチの利点は、任意の部分文字列の長さから開始できることです。 部分文字列をどのように構築する必要がありますか? 先月のブログ投稿で 2 つの解決策を見つけることができます。 1 つ目は、入力文字列を原子化して反復処理します。
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
For(i=1,i<=nInds,i++,
Insert Into(stringList,Concat Items(parts[i::(i + subStringLen - 1)],""))
);
どこinStringは入力文字列で、 subStringLen構築される部分文字列の長さです。 非反復的なアプローチは、式を使用して実装できます。
parts = Items(inString,"");
nInds = Length(inString) - subStringLen + 1;
stringList = {};
i=1;
stringList[1::nInds] = Expr(Concat Items(parts[i::(i++ + subStringLen - 1)],""));
stringList = Eval List(stringList);
またはパターンマッチング
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
各アプローチの速度をテストするために、ランダムに生成された 4 文字で構成される長さ 1,000,000 文字の入力文字列に、サイズ 4、9、15、および 21 の部分文字列を作成しました。 各長さで 10 回の反復が実行されました。 以下の結果は、パターン マッチングの優位性を示しています。 完全な結果は、テスト ビルド Substrings.JMP .
アルゴリズム
|
文字列の長さの構築時間 (秒)
|
4
|
9
|
15
|
21
|
式
|
6.91
|
7.35
|
8.19
|
9.01
|
ループ
|
2.56
|
2.98
|
3.62
|
4.26
|
パターンマッチング
|
1.09
|
1.12
|
1.10
|
1.11
|
アルゴリズム、文字列の長さ、およびアルゴリズム x 文字列の長さの相互作用の統計的差異 (p << 0.001) を示す ANOVA が実行されました。 Tukey の HSD を使用した事後テストでは、パターン マッチング アルゴリズムの文字列の長さのレベル間に統計的な差がないことが示されました。 より大きな文字セットでこのメソッドがどのように実行されるかを確認するために、ランダムに選択された 26 文字から構築された 1,000,000 文字の長い文字列でテストが実行されました。 上記と同じ長さの部分文字列に加えて、2 文字と 40 文字の部分文字列で 20 回の繰り返しが実行されました。 統計的な違いはありましたが、実際の違いはわずかでした。
部分文字列
長さ
|
時間 (秒)
|
2
|
1.11
|
4
|
1.08
|
9
|
1.09
|
15
|
1.11
|
24
|
1.13
|
40
|
1.53
|
部分文字列の作成と重複検索を組み合わせると、次のコードのようになります。 重複に関連付けられた行がわかれば、文字列内のそれらの場所を特定できます。 これは、少し後で有利に働きます。 テーブルをプライベートにすると、操作がわずかに高速化されます。
stringList = {};
Pat Match(inString, Pat Len(subStringLen) >> nextWord+Pat Test(Insert Into(stringList,nextWord);0));
tmpTbl = New Table("tmp",New Column("tmp",Character,Values(stringList)),Private);
sumTbl = tmpTbl << Summary(Group(:tmp),Private);
dupeLocs = sumTbl << Get Rows Where(:N Rows > 1);
dupes = Column(sumTbl,1)[dupeLocs];
Close(tmpTbl,No Save);
以下の表は、Covid-19 と 1,000,000 文字列を使用した 10 回の実行に基づく、1 回の反復の平均実行時間を示しています。 結果を考えると、文字列と部分文字列が大きくなるにつれて、部分文字列サイズの最適化を行わずにこのアプローチを排他的に使用すると問題が生じることが容易にわかります。
部分文字列
長さ
|
COVID 19
|
1M
|
2
|
0.0517
|
1.68
|
4
|
0.0504
|
4.25
|
9
|
0.1837
|
8.29
|
15
|
0.2226
|
8.63
|
21
|
0.2209
|
8.85
|
40
|
0.2957
|
12.30
|
部分文字列のサイズの最適化を開始しても、入力データの構造がどの程度になるかは予測できません。 より良いアプローチは、ハイブリッド戦略を採用することです。 使用まとめ特定のサイズの重複を特定するには、これらの重複のみを使用して、それらから構築できる最長の重複を見つけます。 最長の重複の部分文字列は、短い部分文字列の長さから作成された重複のセットに表示される必要があるため、これは機能します。 考えられるアプローチはいくつかあります。 私は、議論される最終的な方法と類似しているが異なるアプローチを選択します。 正直なところ、私はこのアプローチを思いつく前に最終的な方法を見て、間違いなくその影響を強く受けました。 私が選択したアプローチの課題は、元の部分文字列の位置を追跡するデータ構造を作成することでした。 コードは驚くほど短く、約 50 行と十分な間隔があります。 Covid-19 データのすべての重複を見つけるのに約 0.32 秒、1,000,000 文字の文字列を見つけるのに 13 秒かかります。 コードは次の場所にあります。 findLongestDupe (概要).JSL .
まとめ各反復で重複を見つけるために使用されます。 これは大きなテーブルでは時間がかかりますが、前のステップからの重複数と同じ大きさのテーブルを構築するだけで済みます。 重複を保証するための最小長を 1 文字超える部分文字列の長さから始めると、重複の総数は、すぐにではなくても非常に急速に減少する可能性があります。 数回の反復での行数が多すぎない場合、このメソッドは、より長い部分文字列から開始するなど、さらに最適化せずに使用できます。 この方法の利点は、これらの状況で追加の最適化を使用できることです。 文字列の初期位置を追跡するために使用されるインデックスは、連想配列で使用される場合と同じように機能します。これは、説明する最後の方法で使用されます。 最初の長さの重複文字列の場所を見つけることから始め、それらを一時配列に保存します。 入力文字列の境界を超える文字列を確実に削除して、これらの場所から開始して 1 文字長い文字列を構築します。 このリストで重複する文字列の場所を見つけます。 これらの新しいインデックスを以前に保存した配列へのインデックスとして使用することで、これらの新しいインデックスを元の場所にリンクすることができます。インデックスを持つ要素のみを保持します。 前の配列をこれに置き換えます。 重複がなくなるまで続行します。この時点で、前の配列には最長の重複の場所が含まれます。
前述のように、最終的な方法は前の方法と風味が似ています。 このアプローチのアイデアは、 @ブレイディ_ブレイディ. いくつかの重要な違いがあります。 まず、1 文字からすべての部分文字列を作成します。 これは非効率に思えますが、連想配列を使用し、マトリックスを使用して個々の文字列文字にインデックスを付けることで、文字列を直接検索する必要がなくなり、存在しない文字の組み合わせが回避されます。 一般に、文字セットと入力文字列が大きくなると、前の方法よりもパフォーマンスが向上します。 2 つのアプローチを比較するために、さまざまな入力文字列サイズ (50K ～ 2.5M) と文字セット (4 ～ 72) に対して 10 回の実行が行われました。 要約法 (1) と連想配列法 (2) の平均実行時間を以下に示します。 完全な結果は、最速のメソッドの比較.JMP にあります。
|
50K
|
100K
|
500K
|
1M
|
2.5M
|
文字セットのサイズ
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
2
|
1
|
2
|
4
|
0.5087
|
0.5814
|
0.9081
|
1.2664
|
5.421
|
6.813
|
13.412
|
13.778
|
32.23
|
35.67
|
10
|
0.2724
|
0.4117
|
0.6251
|
0.9207
|
2.850
|
4.509
|
6.998
|
9.503
|
13.61
|
24.70
|
26
|
0.3098
|
0.3748
|
0.6786
|
0.7441
|
3.625
|
3.981
|
7.363
|
8.537
|
21.68
|
19.58
|
52
|
0.4247
|
0.3265
|
1.0617
|
0.7682
|
4.246
|
4.046
|
9.522
|
7.395
|
30.67
|
18.08
|
72
|
0.3186
|
0.3309
|
0.7308
|
0.7079
|
3.533
|
4.236
|
7.192
|
8.917
|
20.14
|
18.97
|
Summary メソッドと同様に、このアプローチは入力文字列を単一の文字に変換することから始まります。 ただし、文字を直接操作するのではなく、文字セットに表示される数値位置が使用されます。 これにより、行列演算を使用して部分文字列を作成できます。これは、文字列演算よりも高速になる傾向があります。 具体的には、最初の反復では、各文字セットの位置の行列表現をキー (G の場合は [3] など) として関連付け配列に取り、入力文字列内の位置のベクトルをその値として使用します。 後続の各反復は、入力文字列の最後の要素を超えないように注意しながら、1 の入力文字列値と前の配列のすべてのキーのベクトル値を見つけることによって、新しい連想配列を構築することから始まります。 インクリメントされたベクトルの最初の要素に対応する値は、残りのインクリメントされたベクトル値の重複を検索するために使用されます。 それらが存在する場合、関連付けられている位置が新しい配列要素の値に使用されます。 この要素のキーは、複製された要素の文字セット値を元のキーに連結することによって構築され、文字列を簡単に再作成できます。 検索値とその重複が存在する場合は、ベクトルから削除され、値がなくなるまで検索が続行されます。 この構築プロセスは、前の配列の各要素に対して発生します。 完了すると、新しい関連配列が古い配列に置き換わり、次の反復が開始されます。 これは、以前の配列を置き換える新しいキーがなくなるまで続きます。 前の配列には、最長の重複が含まれています。
Brady のコードは次の場所にあります。 findLongestDupe (AA).JSL . さまざまな文字セットを使用できるように微調整を行いました。
次回は、文字列からリストに移行します。 以前のブログで述べたように、イテレーションの回避は、最近の 2 つのコミュニティ投稿のトピックでした。数値要素を文字に変換するとリストの索引付け. 次回に向けて2回挑戦。 それらは、リンクされた投稿で出てきた質問に基づいています。 両方の場合において。 数値を文字列に変換しています。
- のリストを変換する関数を書くnリスト（それぞれメートル私数字）。 想定しないでくださいメートル私すべてのリストで同じです。
- 項目 1 からリストを転置できる関数を作成します。 以下に小さな例を示します。
inputList = {{12, 11, 16, 1, 15, ., 23, 8, 16, 17}, {1, 10, ., 4, 25, ., 19, 21, ., 3}, {11, 21,
22, 7, 3, ., 24, 10, 21, 20}, {., ., ., ., ., ., ., ., ., .}, {11, ., 3, ., 9, ., 23,
., 3, 16}};
outputList = {{12, 1, 11, ., 11}, {11, 10, 21, ., .}, {16, ., 22, ., 3}, {1, 4, 7, ., .}, {15, 25,
3, ., 9}, {., ., ., ., .}, {23, 19, 24, ., 23}, {8, 21, 10, ., .}, {16, ., 21, ., 3},
{17, 3, 20, ., 16}}
幸運を！
課題に取り組むための 1 つの方法を次に示します。 私は「仮定しないでください」と決めましたマイルすべてのリストで同じです」ということは、クロスリストに欠損値を埋め込む必要がある可能性があることを意味します。 Repeat({.},10) は {.,.,.,.,.,.,.,.,.,.} を生成します。 Insert() は、リストではなく、リストから項目を追加します (参照リストを別のリストに挿入する方法.)
inputList = {
{12, 11, 16, 1, 15, ., 23, 8, 16, 17},
{1, 10, ., 4, 25, ., 19, 21, ., 3},
{11, 21, 22, 7, 3, ., 24, 10, 21, 20},
{1}, // odd across-list
{., ., ., ., ., ., ., ., ., .},
{11, ., 3, ., 9, ., 23, ., 3, 16}};
// find rows and max cols of input:
nrows = N Items( inputList );
ncols = 0;
For( irow = 1, irow <= nrows, irow += 1,
ncols = Max( ncols, N Items( inputList[irow] ) )
);
// if the across-lists are not all the same size, add missing values
For( irow = 1, irow <= nrows, irow += 1,
If( ncols > N Items( inputList[irow] ),
Insert Into( inputList[irow], Repeat( {.}, ncols - N Items( inputList[irow] ), . ) )
)
);
// make a table of numbers from the lists
dt = New Table( "temp", invisible, Add Rows( nrows ), <<ADD multiple="" columns=""></ADD>この JSL は、リスト内の数値を保持するのに十分な行と数値列を含む、すべて欠落しているデータ テーブルを作成します。 データ テーブルの添え字付けは、長さが不均一な行に満足できず、代入中に数値を文字に変換するのに満足できません。 変換は、SetDataType メッセージを列のリストに送信することによって、最後の方で行われます (明示的な JSL ループを回避します)。転置された数値のリストは、その直前に取得されます。
データ テーブルの添え字は、列がすべて数値である場合、数値行列を介して取得および設定する必要がありますが、数値のリストのリストから問題なく設定されます。 get は行列を返しますが、問題の要件は転置された数値のリストを返すことであるため、AsList() は行列を (データ テーブルから) リストに変換する作業を行います。
