感謝那些嘗試挑戰 7 的人。 希望即使您沒有機會，您也一直在關注討論。 我們如何解決這個挑戰？ 從概念上講，最簡單的方法是找到單個字符重複項，然後是兩個字符重複項、三個字符重複項，以此類推，增加一個字符，直到沒有重複項為止。 天真地檢查給定長度的所有可能字符串隨著子字符串長度的增加而變得越來越耗時。 對於長度約為 30K 個字符的 Covid-19 基因組，即使我們保證有七個字符的子字符串重複項，但只有 4 個7 = 16,384 種獨特組合，僅出現 6889 種 (42%)。 隨著子字符串變長，可能重複的數量迅速增加，重複的數量會減少。 必須找到一種有效的方法來識別重複項，才能使這種方法起作用。 在我們研究了解決這個問題的其他方法之後，我們將回到這個問題。
讓我們專注於找到最長的重複項，而不必擔心找到所有重複項。 一個簡單的方法是在第一個字符處開始子字符串，其中包含七個字符的重複項，因為必須存在一個。 然後，一次增加一個字符，直到沒有重複。 移動到下一個字符和更長的重複子字符串。 繼續此操作，直到您足夠接近搜索字符串的末尾，以至於不可能出現重複。 在 Covid-19 基因組中，一個八字符的子串阿塔阿格可以從第一個字符開始構建。 移動到第二個字符，一個 11 個字符的字符串TTAAAGGTTTA盯著位置 2 在位置 20063 有一個副本。 從位置 3 開始沒有重複的 11 個字符或更長的字符，因此我們移動到位置 4。 等等。 下面的代碼需要大約 5 秒來找到最長的重複字符串，兩個 32 個字符重疊的字符串A秒。 請注意，在下面的代碼中，當與已找到的最長子字符串長度相等的子字符串存在重複項時，儘管在終止之前至少迭代一次。 在這些情況下下一個長度需要減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）進行了十次運行，以比較這兩種方法。 摘要方法 (1) 和關聯數組方法 (2) 的平均運行時間如下所示。 完整的結果可以在 Compare fastest methods.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 方法一樣，此方法首先將輸入字符串轉換為單個字符。 然而，不是直接使用字符，而是使用它們在字符集中出現的數字位置。 這允許使用矩陣運算來構建子串，這往往比字符串運算更快。 具體來說，第一次迭代將每個字符集位置的矩陣表示作為關聯數組的鍵（例如，[3] 表示 G），並使用其在輸入字符串中的位置向量作為其值。 每個後續迭代都從構建一個新的關聯數組開始，方法是找到 1 處的輸入字符串值加上前一個數組中每個鍵的向量值，注意不要超出輸入字符串中的最後一個元素。 與遞增矢量的第一個元素對應的值用於搜索其餘遞增矢量值的重複值。 如果它們存在，則將它們關聯的位置用作新數組元素中的值。 該元素的鍵是通過將重複元素的字符集值連接到原始鍵來構建的，從而可以輕鬆地重新創建字符串。 搜索值及其重複項（如果存在）將從向量中刪除並繼續搜索，直到沒有值為止。 此構建過程針對前一個數組中的每個元素進行。 完成後，新的關聯數組將替換舊的，並開始下一次迭代。 這一直持續到沒有新的鍵來替換以前的數組。 前一個數組包含最長的重複項。
Brady 的代碼可以在findLongestDupe (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() 完成了將矩陣（從數據表）轉換回列表的工作。
