感謝那些嘗試挑戰 7 的人。 希望即使您沒有機會，您也一直在關注討論。 我們如何解決這個挑戰？ 從概念上講，最簡單的方法是尋找單一字符重複項，然後尋找兩個字符重複項、三個字符等，然後增加一個字符，直到沒有重複項。 隨著子字串長度的增加，天真地檢查給定長度的所有可能字串會變得越來越耗時。 對於長度約為 30K 個字元的 Covid-19 基因組，即使我們保證有 7 個字元的子字串重複項，但只有 4 個字符7 = 16,384 個獨特組合，僅出現 6889 個 (42%)。 隨著子串變長，可能重複的數量迅速增加，重複的數量會減少。 為了使這種方法發揮作用，必須找到一種有效的方法來識別重複項。 在我們研究了解決這個問題的其他方法之後，我們將回到這個問題。
讓我們專注於尋找最長的重複項，而不必擔心尋找所有重複項。 一種簡單的方法是在第一個字元處使用七個字元的重複字元開始子字串，因為必須存在一個重複字元。 然後，一次一個字元地增長它，直到沒有重複。 移至下一個字元和更長的重複子字串。 繼續此操作，直到足夠接近搜尋字串的末尾，不可能出現重複項。 在 Covid-19 基因組中，一個八字符的子串攻擊性攻擊可以從第一個字元開始建置。 移動到第二個字符，一個 11 個字符的字串TTAAGGTTTA盯著位置 2，在位置 20063 處有一個重複。 從位置 3 開始，沒有重複的 11 個字符或更長的字符，因此我們移至位置 4。 等等。 下面的程式碼大約需要 5 秒鐘來找到最長的重複字串，兩個 32 個字元的重疊字串A 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 ' 在上一篇部落格文章中發布的程式碼中，我嘗試使用模式匹配來實現上述方法。 令人驚訝的是，結果花了五到六倍的時間。 我不確定到底為什麼，但我的預感是（如上次所示）包含當子字串重複出現的頻率較低時，速度會快得多。
我們可以利用 JMP 內建的重複查找器（即概括表平台。 這種方法的一個優點是我們可以從任何子字串長度開始。 您應該如何建構子字串？ 在上個月的部落格文章中可以找到兩個解決方案。 第一個原子化並迭代輸入字串。
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));
為了測試每種方法的速度，我在由四個隨機生成的字元組成的 1,000,000 個字元長的輸入字串上建立了大小為 4、9、15 和 21 的子字串。 每個長度運行十次迭代。 下面的結果顯示了模式匹配的優越性。 完整的結果可以在測試建構子字串.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)。 使用 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 次的單次迭代的平均運行時間。 根據結果，很容易看出，隨著字串和子字串變大，僅使用此方法而不進行子字串大小優化將會出現問題。
子字串
長度
|
新冠肺炎
|
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 。
概括用於在每次迭代中尋找重複項。 雖然這對於大型表來說很慢，但我們只需要建立與上一步中的重複項數量一樣大的表。 從子字串長度超出保證重複的最小長度一個字元開始，重複的總數可能會減少，如果不是立即減少，那麼很快就會減少。 如果幾次迭代中的行數不太大，則可以使用此方法而無需進一步優化，例如從較長的子字串開始。 這種方法的優點是在這些情況下可以使用額外的最佳化。 用於追蹤初始字串位置的索引以與關聯數組一起使用的方式工作，這就是要討論的最終方法中使用的內容。 首先找到初始長度的重複字串的位置並將它們保存到臨時數組中。 從這些位置開始建立長一個字元的字串，確保刪除任何超出輸入字串邊界的字串。 在此清單中尋找重複字串的位置。 我們可以將這些新索引連結回原始位置，方法是將它們用作先前儲存的陣列的索引，僅保留那些具有索引的元素。 將前一個數組替換為這個數組。 繼續下去，直到沒有重複項，此時前一個陣列包含最長重複項的位置。
如上所述，最終的方法與前一種方法的味道相似。 這種方法的想法歸功於@brady_brady 。 有一些重要的區別。 首先，它從一個字元開始建構所有子字串。 雖然這聽起來效率很低，但透過使用關聯數組並使用矩陣索引各個字串字符，可以消除直接搜尋字串並避免不存在的字符組合。 一般來說，當字元集和輸入字串變大時，它的性能優於以前的方法。 針對不同的輸入字串大小（50K – 2.5M）和字元集（4 至 72）進行了 10 次運行，以比較這兩種方法。 下面顯示了匯總方法 (1) 和關聯數組方法 (2) 的平均運行時間。 完整的結果可以在比較最快的方法.JMP 中找到。
|
50K
|
10萬
|
50萬
|
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 處的輸入字串值加上前一個數組中每個鍵的向量值來建立一個新的關聯數組，注意不要超出輸入字串中的最後一個元素。 與遞增向量的第一個元素相對應的值用於搜尋其餘遞增向量值的重複項。 如果它們存在，則它們關聯的位置將用作新數組元素中的值。 該元素的鍵是透過將重複元素的字元集值連接到原始鍵來建構的，從而可以輕鬆地重新建立字串。 搜尋值及其重複項（如果存在）將從向量中刪除，並繼續搜索，直到沒有值留下。 此建置過程針對前一個陣列中的每個元素進行。 完成後，新的關聯數組將取代舊的關聯數組，並開始下一個迭代。 這一直持續到沒有新的鍵來替換先前的陣列為止。 前一個陣列包含最長的重複項。
布雷迪代碼可以在以下位置找到尋找最長重複項 (AA).JSL 。 我做了一個小的調整，以允許使用不同的字元集。
下次我們將從字串轉向列表。 正如上一篇部落格中提到的，避免迭代是最近兩篇社群貼文的主題，其中涉及將數字元素轉換為字符和列表索引。 下次有兩個挑戰。 它們基於連結帖子中提出的問題。 在這兩種情況下。 您正在將數值轉換為字串。
- 編寫一個函數來隱藏列表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}}
祝你好運！
這是應對這項挑戰的一種方法。 我決定「不要假設米對於所有列表都是相同的”意味著跨列表可能需要用缺失值填充。 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() 完成將矩陣（來自資料表）轉換回列表的工作。
