チャレンジ 7 を試してくださった方々に感謝します。 たとえ機会がなかったとしても、ディスカッションに注目していただければ幸いです。 この課題をどうやって解決できるでしょうか? 概念的には、最も単純なアプローチでは、1 文字の重複が検出され、次に 2 文字の重複、3 文字というように、重複がなくなるまで 1 文字ずつ増加します。 与えられた長さについて考えられるすべての文字列を単純にチェックすると、部分文字列の長さが増すにつれて時間がかかるようになります。 約 30,000 文字の長さの Covid-19 ゲノムの場合、7 文字の部分文字列の重複が保証されているにもかかわらず、重複するのは 4 文字だけです7 = 16,384 の一意の組み合わせのうち、6,889 のみ (42%) が発生します。 また、部分文字列が長くなると、重複の可能性が急速に増加するため、重複の数は減少します。 このアプローチを機能させるには、重複を識別する効率的な方法を見つける必要があります。 この問題に取り組む他の方法を検討した後で、この問題に戻ります。
すべての重複を見つけることを心配せずに、最長の重複を見つけることだけに集中しましょう。 簡単な方法は、7 文字の重複が存在する必要があるため、部分文字列を最初の文字で開始することです。 次に、重複がなくなるまで一度に 1 文字ずつ成長させます。 次の文字と、より長い重複部分文字列に移動します。 重複が不可能になる検索文字列の末尾に近づくまで、これを続けます。 Covid-19 ゲノムでは、8 文字の部分文字列アッタアアグ最初の文字から構築できます。 2 文字目の 11 文字の文字列に移動たぁぁぁぁぁぁぁぁぁ位置 2 を見つめると、位置 20063 に重複があります。 位置 3 から始まる 11 文字以上の重複がないため、位置 4 に移動します。 等々。 以下のコードでは、最も長い重複文字列 (32 文字の 2 つの重複文字列) を見つけるのに約 5 秒かかります。あs. 以下のコードでは、すでに見つかった最長の部分文字列と同じ長さの部分文字列に重複が存在する場合、その間終了する前に少なくとももう一度繰り返します。 このような状況では次のレン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)],""))
);
どこ文字列内は入力文字列であり、サブストリングレン構築される部分文字列の長さです。 非反復的なアプローチは、式を使用して実装できます。
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 回の反復を実行しました。 以下の結果はパターンマッチングの優位性を示しています。 完全な結果は次の場所にあります。テスト ビルド サブストリング.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
|
ANOVA が実行され、アルゴリズム、文字列長、およびアルゴリズム x 文字列長の相互作用に関する統計的差異 (p << 0.001) が示されました。 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 文字長の文字列を作成し、入力文字列の境界を超える文字列を必ず削除します。 このリストで重複する文字列の場所を見つけます。 これらの新しいインデックスを、インデックスを持つ要素のみを保持する以前に保存した配列へのインデックスとして使用することで、元の場所にリンクし戻すことができます。 前の配列をこの配列に置き換えます。 重複がなくなるまで続けます。重複がなくなると、前の配列に最長の重複の位置が含まれます。
上で述べたように、最終的なメソッドは前のメソッドと雰囲気が似ています。 このアプローチのアイデアは次のおかげです。 @brady_brady 。 重要な違いがいくつかあります。 まず、1 文字からすべての部分文字列を構築します。 これは非効率的に聞こえますが、連想配列を使用し、行列を使用して個々の文字列文字にインデックスを付けることにより、文字列を直接検索する必要がなくなり、存在しない文字の組み合わせが回避されます。 一般に、文字セットと入力文字列が大きくなると、以前の方法よりも優れたパフォーマンスが得られます。 2 つのアプローチを比較するために、さまざまな入力文字列サイズ (50K ～ 2.5M) と文字セット (4 ～ 72) に対して 10 回の実行が行われました。 Summary メソッド (1) と Associative Array メソッド (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 つの最近のコミュニティ投稿のトピックとなっています。数値要素を文字に変換するそしてリストのインデックス作成。 次回の課題は２つ。 これらは、リンクされた投稿で出た質問に基づいています。 両方の場合において。 数値を文字列に変換しています。
- のリストを変換する関数を作成します。 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 は、リスト内の数値を保持するのに十分な行と数値列を備えた全欠損データ テーブルを作成します。 データ テーブルの添字付けは行の長さが不均一であることに満足せず、代入中に数値を文字に変換することにも満足できません。 変換は、(明示的な JSL ループを回避して) 列のリストに SetDataType メッセージを送信することによって、最後の近くで行われます。その直前に、転置された数値のリストがキャプチャされます。
データ テーブルの添字付けでは、列がすべて数値の場合、数値行列を介して取得および設定する必要がありますが、数値のリストのリストから問題なく設定されます。 get は行列を返すことになりますが、問題の要件は転置された数値のリストを返すことであるため、AsList() は行列を (データ テーブルから) リストに変換して戻します。
