(19)國家知識產(chǎn)權局(12)發(fā)明專利(65)同一申請的已公布的文獻號(30)優(yōu)先權數(shù)據(jù)(85)PCT國際申請進入國家階段日(86)PCT國際申請的申請數(shù)據(jù)(87)PCT國際申請的公布數(shù)據(jù)(73)專利權人甲骨文國際公司地址美國加利福尼亞(74)專利代理機構中國貿(mào)促會專利商標事務所有限公司11038專利代理師張鑫HO4L67/01(2022.01)US2018113894A1,2018.0(54)發(fā)明名稱基于肯定和否定模式匹配示例的正則表達式生成本文公開的是與正則表達式的自動生成相關的技術。在一些實施例中，正則表達式生成器可以接收包括一個或多個字符序列的輸入數(shù)據(jù)。正則表達式生成器可以將字符序列轉換成正則表達式代碼和/或跨度數(shù)據(jù)結構的集合。正則表達式生成器可以標識由正則表達式代碼和/或跨客戶端設備web瀏覽器客戶rege正則表達式生成服務器regex庫2由包括一個或多個處理器的正則表達式生成器接收包括一個或多個肯定字符序列的第一輸入數(shù)據(jù)，所述一個或多個肯定字符序列中的每一個對應于要與所述正則表達式生成器生成的正則表達式匹配的肯定示例；由所述正則表達式生成器生成第一正則表達式，其中所述第一正則表達式與所述一個或多個肯定示例中的每一個匹配；由所述正則表達式生成器接收包括一個或多個否定字符序列的第二輸入數(shù)據(jù)，所述一個或多個否定字符序列中的每一個對應于要與所述正則表達式生成器生成的正則表達式不匹配的否定示例；響應于接收到所述第二輸入數(shù)據(jù)，確定所述一個或多個否定示例中的每一個是否與所響應于確定至少一個否定示例與所述第一正則表達式匹配：(a)確定所述第一正則表達式內(nèi)的位置處的字符子序列；(b)確定替換字符序列，其中所述正則表達式內(nèi)的所述位置處的替換字符序列區(qū)分所述一個或多個肯定示例與所述一個或多個否定示例；以及(c)通過用所述替換字符序列替換所述第一正則表達式內(nèi)的所確定的字符子序列來更新所述第一正則表達式。2.如權利要求1所述的方法，其中確定所述第一正則表達式內(nèi)的所述位置處的字符子序列包括：確定所述第一正則表達式內(nèi)的所述位置；從所述一個或多個肯定示例中的每一個以及從所述一個或多個否定示例中的每一個檢索對應于所述第一正則表達式內(nèi)的所述位置的文本片段；以及將所述字符子序列確定為所述第一正則表達式內(nèi)的所述位置處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的一個或多個字符。3.如權利要求2所述的方法，其中確定所述第一正則表達式內(nèi)的所述位置包括：確定所述第一正則表達式的前綴部分處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的第一數(shù)量的字符；確定所述第一正則表達式的后綴部分處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的第二數(shù)量的字符；以及至少部分地基于所述第一數(shù)量的字符還是所述第二數(shù)量的字符較短來選擇所述前綴部分或是所述后綴部分作為所述第一正則表達式內(nèi)的所述位置。4.如權利要求3所述的方法，其中確定所述第一正則表達式內(nèi)的所述位置還包括：執(zhí)行公式以確定所述第一正則表達式內(nèi)的所述位置，其中所述公式將所述第一正則表達式的所述前綴部分相對于所述后綴部分加重。5.如權利要求2所述的方法，其中所述第一正則表達式內(nèi)的所確定的位置是不對應于所述第一正則表達式的前綴部分或所述第一正則表達式的后綴部分的中間跨度位置。6.如權利要求2所述的方法，其中確定所述替換字符序列包括確定多個替換字符序列，并且其中更新所述第一正則表達式包括用所述多個替換字符序列替換所述第一正則表達式內(nèi)的所確定的字符子序列。37.如權利要求1所述的方法，其中確定所述替換字符序列包括：確定所述第一正則表達式內(nèi)的所述位置處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的第一數(shù)量的字符以及相應的第一數(shù)量的替換字符序列，所述相應的第一數(shù)量的替換字符序列中的每個替換字符序列具有所述第一數(shù)量的字符；確定所述第一正則表達式內(nèi)的所述位置處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的第二數(shù)量的字符以及相應的第二數(shù)量的替換字符序列，所述相應的第二數(shù)量的替換字符序列中的每個替換字符序列具有所述第二數(shù)量的字符；以及基于(a)所述第一數(shù)量的字符和所述第二數(shù)量的字符的大小以及(b)所述相應的第一數(shù)量的替換字符序列和所述相應的第二數(shù)量的替換字符序列的大小，選擇所述第一數(shù)量的字符或所述第二數(shù)量的字符用于所述第一正則表達式內(nèi)的替換字符序列。8.一種用于生成正則表達式的系統(tǒng)，所述系統(tǒng)包括：包括一個或多個處理器的處理單元；以及存儲指令的存儲器，所述指令當由所述處理單元執(zhí)行時使得所述系統(tǒng)：接收包括一個或多個肯定字符序列的第一輸入數(shù)據(jù)，所述一個或多個肯定字符序列中的每一個對應于要與所述正則表達式生成器生成的正則表達式匹配的肯定示例；生成第一正則表達式，其中所述第一正則表達式與所述一個或多個肯定示例中的每一個匹配；接收包括一個或多個否定字符序列的第二輸入數(shù)據(jù)，所述一個或多個否定字符序列中的每一個對應于要與所述正則表達式生成器生成的正則表達式不匹配的否定示例；響應于接收到所述第二輸入數(shù)據(jù)，確定所述一個或多個否定示例中的每一個是否與所響應于確定至少一個否定示例與所述第一正則表達式匹配：(a)確定所述第一正則表達式內(nèi)的位置處的字符子序列；(b)確定替換字符序列，其中所述正則表達式內(nèi)的所述位置處的替換字符序列區(qū)分所述一個或多個肯定示例與所述一個或多個否定示例；以及(c)通過用所述替換字符序列替換所述第一正則表達式內(nèi)的所確定的字符子序列來更新所述第一正則表達式。9.如權利要求8所述的系統(tǒng)，其中確定所述第一正則表達式內(nèi)的所述位置處的字符子序列包括：確定所述第一正則表達式內(nèi)的所述位置；從所述一個或多個肯定示例中的每一個以及從所述一個或多個否定示例中的每一個檢索對應于所述第一正則表達式內(nèi)的所述位置的文本片段；以及將所述字符子序列確定為所述第一正則表達式內(nèi)的所述位置處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的一個或多個字符。10.如權利要求9所述的系統(tǒng)，其中確定所述第一正則表達式內(nèi)的所述位置包括：確定所述第一正則表達式的前綴部分處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的第一數(shù)量的字符；確定所述第一正則表達式的后綴部分處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的第二數(shù)量的字符；以及4至少部分地基于所述第一數(shù)量的字符還是所述第二數(shù)量的字符較短來選擇所述前綴部分或是所述后綴部分作為所述第一正則表達式內(nèi)的所述位置。11.如權利要求10所述的系統(tǒng)，其中確定所述第一正則表達式內(nèi)的所述位置還包括：執(zhí)行公式以確定所述第一正則表達式內(nèi)的所述位置，其中所述公式將所述第一正則表達式的所述前綴部分相對于所述后綴部分加重。12.如權利要求9所述的系統(tǒng)，其中所述第一正則表達式內(nèi)的所確定的位置是不對應于所述第一正則表達式的前綴部分或所述第一正則表達式的后綴部分的中間跨度位置。13.如權利要求9所述的系統(tǒng)，其中確定所述替換字符序列包括確定多個替換字符序列，并且其中更新所述第一正則表達式包括用所述多個替換字符序列替換所述第一正則表達式內(nèi)的所確定的字符子序列。14.如權利要求8所述的系統(tǒng)，其中確定所述替換字符序列包括：確定所述第一正則表達式內(nèi)的所述位置處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的第一數(shù)量的字符以及相應的第一數(shù)量的替換字符序列，所述相應的第一數(shù)量的替換字符序列中的每個替換字符序列具有所述第一數(shù)量的字符；確定所述第一正則表達式內(nèi)的所述位置處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的第二數(shù)量的字符以及相應的第二數(shù)量的替換字符序列，所述相應的第二數(shù)量的替換字符序列中的每個替換字符序列具有所述第二數(shù)量的字符；以及基于(a)所述第一數(shù)量的字符和所述第二數(shù)量的字符的大小以及(b)所述相應的第一數(shù)量的替換字符序列和所述相應的第二數(shù)量的替換字符序列的大小，選擇所述第一數(shù)量的字符或所述第二數(shù)量的字符用于所述第一正則表達式內(nèi)的替換字符序列。15.一種用于生成正則表達式的非暫態(tài)計算機可讀介質，所述計算機可讀介質包括計算機可執(zhí)行指令，所述計算機可執(zhí)行指令在計算機系統(tǒng)上執(zhí)行時使得所述計算機系統(tǒng)：接收包括一個或多個肯定字符序列的第一輸入數(shù)據(jù)，所述一個或多個肯定字符序列中的每一個對應于要與所述正則表達式生成器生成的正則表達式匹配的肯定示例；生成第一正則表達式，其中所述第一正則表達式與所述一個或多個肯定示例中的每一個匹配；接收包括一個或多個否定字符序列的第二輸入數(shù)據(jù)，所述一個或多個否定字符序列中的每一個對應于要與所述正則表達式生成器生成的正則表達式不匹配的否定示例；響應于接收到所述第二輸入數(shù)據(jù)，確定所述一個或多個否定示例中的每一個是否與所響應于確定至少一個否定示例與所述第一正則表達式匹配：(a)確定所述第一正則表達式內(nèi)的位置處的字符子序列；(b)確定替換字符序列，其中所述正則表達式內(nèi)的所述位置處的替換字符序列區(qū)分所述一個或多個肯定示例與所述一個或多個否定示例；以及(c)通過用所述替換字符序列替換所述第一正則表達式內(nèi)的所確定的字符子序列來更新所述第一正則表達式。16.如權利要求15所述的計算機可讀介質，其中確定所述第一正則表達式內(nèi)的所述位置處的字符子序列包括：確定所述第一正則表達式內(nèi)的所述位置；5從所述一個或多個肯定示例中的每一個以及從所述一個或多個否定示例中的每一個檢索對應于所述第一正則表達式內(nèi)的所述位置的文本片段；以及將所述字符子序列確定為所述第一正則表達式內(nèi)的所述位置處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的一個或多個字符。17.如權利要求16所述的計算機可讀介質，其中確定所述第一正則表達式內(nèi)的所述位確定所述第一正則表達式的前綴部分處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的第一數(shù)量的字符；確定所述第一正則表達式的后綴部分處的能夠區(qū)分所述一個或多個肯定示例和所述一個或多個否定示例的第二數(shù)量的字符；以及至少部分地基于所述第一數(shù)量的字符還是所述第二數(shù)量的字符較短來選擇所述前綴部分或是所述后綴部分作為所述第一正則表達式內(nèi)的所述位置。18.如權利要求17所述的計算機可讀介質，其中確定所述第一正則表達式內(nèi)的所述位置還包括：執(zhí)行公式以確定所述第一正則表達式內(nèi)的所述位置，其中所述公式將所述第一正則表達式的所述前綴部分相對于所述后綴部分加重。19.如權利要求16所述的計算機可讀介質，其中所述第一正則表達式內(nèi)的所確定的位置是不對應于所述第一正則表達式的前綴部分或所述第一正則表達式的后綴部分的中間跨度位置。20.如權利要求16所述的計算機可讀介質，其中確定所述替換字符序列包括確定多個替換字符序列，并且其中更新所述第一正則表達式包括用所述多個替換字符序列替換所述第一正則表達式內(nèi)的所確定的字符子序列。21.一種計算機程序產(chǎn)品，包括指令，所述指令在由計算機執(zhí)行時，使得所述計算機執(zhí)行如權利要求1-7中任一項所述的方法。6[0002]本申請根據(jù)35U.S.C.§119(e)要求于2018年6月1本申請還根據(jù)35U.S.C.§119(e)要求于2018年10月22日提交的、題為“AUTOMATED臨時專利申請?zhí)?2/684,498和62/749,001的全部內(nèi)容通過引用合并于此以供用于所有目構化數(shù)據(jù)。這種數(shù)據(jù)的存儲庫通常包括各種不同格式和結[0004]對數(shù)據(jù)格式化和預處理問題的許多當前解決方案包括手動和adhoc處理以清理和較小的數(shù)據(jù)集可能是有效的，但是當試圖對大規(guī)模數(shù)據(jù)集進行預可以用于匹配字符串和/或從作為輸入提供的字符串中提取信息。在本文描述的各種實施由一個或多個正則表達式代碼的不同集合共享的所確定的最長通用子序列(LCS)來生成正7代碼的每個集合可以從作為輸入數(shù)據(jù)通過用戶界面接收的一個或多個字符的不同序列轉換。從LCS中排除的正則表達式代碼可以被表示為可選的和/或備選的。在一些實施例中，正則表達式代碼可以與該正則表達式代碼的最小出現(xiàn)次數(shù)相關聯(lián)。附加地或備選地，正則表達式代碼可以與正則表達式代碼的最大出現(xiàn)次數(shù)相關聯(lián)。例如，類別代碼集合可以包括L<0,1>,以指示LCS的特定部分包括字母最多一次(如果有的話)。如下面更詳細討論的，將輸入數(shù)據(jù)概括為中間正則表達式代碼(IREC)可以提供各種技術優(yōu)勢，包括使用非常少的輸入數(shù)據(jù)，使得能夠近乎即時地生成不被尚未看到的數(shù)據(jù)中的假陽性匹配或假陰性匹配影響的正則表達式。[0007]根據(jù)本文描述的附加方面，可以基于包括三個或更多個字符序列的輸入數(shù)據(jù)來生成正則表達式。當三個或更多字符序列被標識為輸入數(shù)據(jù)時，標識字符序列的LCS的正則表達式生成器可能導致運行時間的指數(shù)增加。為了以高性能方式標識所有字符序列的LCS,正則表達式生成器可以對兩個字符序列的每個不同組合執(zhí)行LCS算法。可以基于LCS算法的結果生成全連接的圖，其中每個圖節(jié)點代表不同的字符序列，并且每個圖邊的長度對應于定義圖邊的節(jié)點的LCS。然后，可以通過對全連接圖的最小生成樹執(zhí)行深度優(yōu)先遍歷來確定選擇字符序列的順序。[0008]本文描述的其他方面涉及基于包括肯定字符序列示例和否定字符序列示例兩者的輸入來生成正則表達式?？隙ㄊ纠梢灾概c要生成的正則表達式匹配的字符序列，而否定示例可以指與要生成的正則表達式不匹配的字符序列。在一些實施例中，當接收到肯定示例和否定示例兩者時，正則表達式生成器可以識標識將肯定示例和否定示例區(qū)分開的一個或多個字符的鑒別符或最短子序列。所選擇的鑒別符可以是最短序列(例如，以類別代碼表示),并且可以是肯定的或否定的，使得肯定示例將匹配而否定示例將不匹配。然后，可以將鑒別符硬編碼到由正則表達式生成器生成的正則表達式中。在一些情況下，最短子序列可以包括在否定示例的前綴或后綴部分中。[0009]本文描述的附加方面涉及可通過其提供輸入數(shù)據(jù)以生成正則表達式的一個或多個用戶界面。在一些實施例中，可以在通信地耦合到正則表達式生成器服務器的客戶端設備處顯示用戶界面。用戶界面可以由服務器、由客戶端設備、或由在服務器和客戶端執(zhí)行的軟件組件的組合以編程方式生成。通過用戶界面接收的輸入數(shù)據(jù)可以對應于用戶對一個或多個字符序列的選擇，這些字符序列可以代表肯定或否定示例。在一些情況下，用戶界面可以支持包括在第二字符序列內(nèi)對第一字符序列的選擇的輸入數(shù)據(jù)。例如，用戶可以突出顯示較大的先前突出顯示的字符序列中的一個或多個字符，并且第二用戶選擇可以針對較大的第一用戶選擇提供上下文。這使得輸入數(shù)據(jù)能夠更有針對性地被提供給正則表達式生成器，并且為正則表達式生成器提供“上下文”,使得它可以生成避免假應于用戶經(jīng)由用戶界面選擇字符序列，正則表達式生成器可以生成并顯示正則表達式。例如，當用戶突出顯示第一字符序列時，正則表達式生成器可以生成并顯示匹配第一字符序列以及其他相似字符序列(例如，與用戶針對匹配序列的意圖一致)的正則表達式。當用戶突出顯示第二字符序列時，正則表達式生成器可以生成包含第一和第二字符序列的更新的正則表達式。然后，當用戶突出顯示第三字符序列(例如，在第一或第二序列內(nèi))時，正則表達式生成器可以再次更新正則表達式，以此類推。8[0010]根據(jù)本文描述的附加方面，正則表達式可以基于來自一個或多個輸入序列示例的最長通用子序列來生成，也可以處理僅在一些示例中出現(xiàn)的字符。為了處理僅在一些輸入示例中出現(xiàn)的字符，可以定義跨度，其中追蹤正則表達式代碼的最小和最大出現(xiàn)次數(shù)。在跨度可能不存在于所有給定輸入示例的情況下，可以將最小出現(xiàn)次數(shù)設置為零。然后可以將這些最小和最大數(shù)字映射到正則表達式重度語法。最長通用子序列(LCS)算法可以在從輸入示例得到的字符的跨度上運行，包括并非在每個輸入示例中都出現(xiàn)的“可選的”跨度(例如，最小長度為零)。如下文所討論的，可以在LCS算法的執(zhí)行期間合并連續(xù)跨度。在這種情況下，當攜帶的額外可選跨度不再連續(xù)出現(xiàn)時，LCS算法也可以在這些可選跨度上遞歸運行。[0011]本文描述的其他方面涉及組合搜索，其中由正則表達式生成器執(zhí)行的LCS算法可以被多次運行以生成“正確的”正則表達式(例如，與所有給定的肯定示例正確匹配并且適當?shù)嘏懦薪o定的否定示例的正則表達式),和/或生成多個正確的正則表達式，從中可以選擇最期望的或最佳的正則表達式。在一些實施例中，通常可以對輸入示例從右向左執(zhí)行LCS算法以生成正則表達式。然而，出于比較的目的并為了找到備選的正則表達式，LCS算法可以在輸入示例上向后(例如，在從左到右的方向上)分別執(zhí)行。例如，作為用戶輸入接收的示例字符序列可以在它們運行LCS算法之前被顛倒，然后來自LCS算法的結果可以被顛倒回來(包括原始文本片段)。此外，在一些實施例中，LCS算法可以由正則表達式生成器運行多次，以通常的字符序列順序和相反的順序，在行首錨定，在行尾錨定，在行首或行尾不錨的成功正則表達式。附圖說明[0012]圖1是示出用于生成正則表達式的示例性分布式系統(tǒng)的組件的框圖，其中可以實現(xiàn)各種實施例。[0013]圖2是根據(jù)本文描述的一個或多個實施例，示出基于經(jīng)由用戶界面接收的輸入來生成正則表達式的過程的流程圖。[0014]圖3是根據(jù)本文描述的一個或多個實施例，示出在正則表達式代碼集合上使用最長通用子序列(LCS)算法來生成正則表達式的過程的流程圖。[0015]圖4是根據(jù)本文描述的一個或多個實施例，基于兩個字符序列示例、在正則表達式代碼集合上使用最長通用子序列(LCS)算法來生成正則表達式的示例圖。[0016]圖5是根據(jù)本文描述的一個或多個實施例，示出在較大的正則表達式代碼集合上使用最長通用子序列(LCS)算法來生成正則表達式的過程的流程圖。[0017]圖6是根據(jù)本文描述的一個或多個實施例，基于五個字符序列示例、在正則表達式代碼集合上使用最長通用子序列(LCS)算法來生成正則表達式的示例圖。[0018]圖7是根據(jù)本文描述的一個或多個實施例，示出用于在較大的正則表達式代碼集合上確定針對最長通用子序列(LCS)算法的執(zhí)行順序的過程的流程圖。[0019]圖8A和8B根據(jù)本文描述的一個或多個實施例，示出了全連接圖和全連接圖的最小生成樹表示，用于在較大的正則表達式代碼集合上確定針對最長通用子序列(LCS)算法的執(zhí)行順序。9[0020]圖9是根據(jù)本文描述的一個或多個實施例，示出基于肯定和否定字符序列示例來生成正則表達式的過程的流程圖。[0021]圖10A和10B是根據(jù)本文描述的一個或多個實施例，示出基于肯定和否定字符序列示例生成正則表達式的示例用戶界面屏幕。[0022]圖11是根據(jù)本文描述的一個或多個實施例，示出基于在用戶界面內(nèi)接收的用戶數(shù)據(jù)選擇來生成正則表達式的過程的流程圖。[0023]圖12是根據(jù)本文描述的一個或多個實施例，示出用于基于捕獲組，經(jīng)由在用戶界面內(nèi)接收的用戶數(shù)據(jù)選擇生成正則表達式和提取數(shù)據(jù)的流程圖。[0024]圖13是根據(jù)本文描述的一個或多個實施例，示出表格數(shù)據(jù)顯示的示例用戶界面屏幕。[0025]圖14和15是根據(jù)本文描述的一個或多個實施例，示出基于來自表格顯示的數(shù)據(jù)選擇來生成正則表達式和捕獲組的示例用戶界面屏幕。[0026]圖16A和16B是根據(jù)本文描述的一個或多個實施例，示出基于來自表格顯示的肯定和否定示例選擇來生成正則表達式的示例用戶界面屏幕。[0027]圖17是根據(jù)本文描述的一個或多個實施例，示出基于來自表格顯示的數(shù)據(jù)選擇來生成正則表達式和捕獲組的另一示例用戶界面屏幕。[0028]圖18是根據(jù)本文描述的一個或多個實施例，示出使用最長通用子序列(LCS)算法生成包括可選跨度的正則表達式的過程的流程圖。[0029]圖19是根據(jù)本文描述的一個或多個實施例，使用最長通用子序列(LCS)算法生成包括可選跨度的正則表達式的示例圖。[0030]圖20是根據(jù)本文描述的一個或多個實施例，示出基于最長通用子序列(LCS)算法的組合執(zhí)行來生成正則表達式的過程的流程圖。[0031]圖21是示出可以實現(xiàn)本發(fā)明的各種實施例的示例性分布式系統(tǒng)的組件的框圖。[0032]圖22是示出可以將由本發(fā)明的實施例提供的服務提供為云服務的系統(tǒng)環(huán)境的組件的框圖。[0033]圖23是示出可以實現(xiàn)本發(fā)明的實施例的示例性計算機系統(tǒng)的框圖。具體實施方式[0034]在下面的描述中，出于解釋的目的，呈現(xiàn)了許多具體細節(jié)，以便提供對本發(fā)明的各種實施例的透徹理解。然而，對于本領域技術人員來說顯而易見的是，本發(fā)明的實施例可以在沒有這些具體細節(jié)的情況下實施。在其他情況下，公知的結構和設備以框圖形式示出。[0035]下面的描述僅提供示例性實施例，并不意圖限制本公反，下面對示例性實施例的描述將向本領域技術人員提供用于實現(xiàn)示例性實施例的實現(xiàn)描述。應當理解，在不背離所附權利要求中陳述的本發(fā)明的精神和范圍的情況下，可以在元件的功能和布置上進行各種改變。[0036]在下面的描述中給出具體細節(jié)以提供對實施例的透徹理解。然而，本領域普通技程和其他組件可被示為框圖形式的組件，以便不在不必要的細節(jié)中混淆實施例。在其他情結構和技術。[0037]還要注意的是，各個實施例可以被描述為過程，該過程被描繪為流程圖表、流程圖、數(shù)據(jù)流程圖、結構圖或框圖。雖然流程圖可以將操作描述為順序過程，但許多操作可以并行或并發(fā)執(zhí)行。此外，可以重新安排操作的順序。過程在其操作完成時終止，但可能有圖函數(shù)時，其終止可以對應于函數(shù)返回到調(diào)用函數(shù)或主函數(shù)。[0038]術語“計算機可讀介質”包括但不限于諸如便攜式或固定存儲設備的非暫態(tài)介質、光學存儲設備、以及能夠存儲、包含或攜帶指令和/或數(shù)據(jù)的各種其他介質。代碼段或計算據(jù)結構或程序語句的任意組合。代碼段可以通過傳遞和/或接收信息、存儲器內(nèi)容而耦合到另一代碼段或硬件電路。信息、自變量、參數(shù)、數(shù)據(jù)等可以經(jīng)由包括存合來實現(xiàn)。當以軟件、固件、中間件或微碼實現(xiàn)時，用于執(zhí)行必要任務的程序代碼或代碼段可以被存儲在機器可讀介質中。處理器可以執(zhí)行必要任務。[0040]本文描述了用于生成對應于在一個或多個輸入數(shù)據(jù)示例中標識的模式的正則表達式的各種技術(例如，方法、系統(tǒng)、存儲可由一個或多個處理器執(zhí)行的多個指令的非暫態(tài)計算機可讀存儲器等)。在某些實施例中，響應于接收到對輸入數(shù)據(jù)的選擇，自動標識輸入數(shù)據(jù)中的一個或多個模式，并且可以自動且高效地生成正則表達式(或簡稱“regex”)以表序列)。本文描述了各種實施例，包括方法、系統(tǒng)、存儲可由一個或多個處理器執(zhí)行的程序、代碼或指令的非暫態(tài)計算機可讀存儲介質等。[0041]在一些實施例中，可以使用符號通配符匹配語言來組成正則表達式，以便匹配字符串和/或從作為輸入提供的字符串中提取信息。例如，第一示例正則表達式[A-Za-z]{3}\d?\d,\d\d\d\d可以匹配某些日期(例如，2018年4月3日),并且第二示例正則表達式[A-Za-z]{3}\d?\d,(\d\d\d\d)可以用于從匹配日期中提取年份。正則表達式生成器系統(tǒng)接收的如本文所使用的，肯定示例可以指作為輸入接收的，要與基于該輸入生成的正則表達式匹配的字符序列。相反，否定示例可以指要與基于該輸入生成的正則表達式不匹配的輸入字符序列。[0042]在本文描述的各種實施例和示例內(nèi)可以實現(xiàn)許多技術優(yōu)勢。例如，本公開中描述的某些技術可以提高正則表達式生成過程的速度和效率(例如，regex解決方案可以在不到一秒內(nèi)生成，并且用戶界面可以適合于交互式實時使用)。本文描述的各種技術也可以是確定性的，可以不需要訓練數(shù)據(jù)，可以在不需要任何初始正則表達式輸入的情況下產(chǎn)生解決方案，并且可以完全自動化(例如，在不需要任何人工干預的情況下生成正則表達式)。此外，本文描述的各種技術不需要限制可以被有效處理的數(shù)據(jù)輸入的類型，并且這樣的技術可以提高所得到的正則表達式的人類可讀性。[0043]本文描述的某些實施例包括最長通用子序列(LCS)算法的一個或多個執(zhí)行。LCS算法可以在某些上下文中用作差異引擎(例如，Unix“diff”實用程序背后的引擎),其被配置11為確定并顯示兩個文本文件之間的差異。在一些實施例中，可以將輸入數(shù)據(jù)(例如，字符串和其他字符序列)轉換成抽象令牌，然后可以將抽象令牌作為輸入提供給LCS算法。這樣的抽象令牌可以是例如基于表示正則表達式字符類的正則表達式代碼(例如，Loogle代碼或其他字符類代碼)的令牌。這種代碼的各種不同示例是可能的，并且本文可以被稱為“正則IREC碼“LLLZN”,之后可以向LCS算法提供該令牌化的字符串以及其他令牌化的字符串。在一些實施例中，輸入字符序列不通用擁有的IREC(例如，正則表達式代碼)可以作為可選(例如，可選的跨度)出現(xiàn)在最終生成的正則表達式中。在某些實施例中，正則表達式代碼可以是基于/unicode.html#category所示的UNICODE類別代碼的類別代碼。例如，代碼L可以代表字母，代碼N可以代表數(shù)字，代碼Z可以代表空{(diào)L},而代碼N可以對應于Unicode\p{N}。這允許從LCS輸出到正則表達式的一對一映射(例相交的，使得類別的成員之間可以不存在重疊。[0044]在各種實施例中可以實現(xiàn)附加的技術優(yōu)勢，包括基于正則表達式代碼(例如，類別代碼)、跨度等的使用來更有效地生成正則表達式。通過使用這樣的代碼，當LCS算法成功地將輸入字符串中的所有或基本上所有字符標識為不同時，不需要浪費計算資源。本文的各種實施例提供的其他技術優(yōu)勢包括改進的所生成的正則表達式的可讀性，以及支持作為輸入數(shù)據(jù)的肯定示例和否定示例，以及提供各種有利的用戶界面特征(例如，允許用戶突出顯示較大字符序列或數(shù)據(jù)單元內(nèi)的文本片段以供提取)。[0045]I.總體概述[0046]本文公開的各種實施例涉及正則表達式的生成。在一些實施例中，被配置為正則表達式生成器的數(shù)據(jù)處理系統(tǒng)可以通過標識由不同的正則表達式代碼(例如，類別代碼)的集合共享的最長通用子序列(LCS)來生成正則表達式。每個正則表達式代碼集合可以從作為輸入數(shù)據(jù)通過用戶界面接收的字符序列轉換。在本文描述的技術優(yōu)勢中，將輸入數(shù)據(jù)抽象為中間代碼(例如，正則表達式代碼、跨度等)可以實現(xiàn)使用非常少的輸入數(shù)據(jù)高效地生成正則表達式。[0047]圖1是示出用于生成正則表達式的示例性分布式系統(tǒng)的組件的框圖，其中可以實現(xiàn)各種實施例。如該示例中所示，客戶端設備120可以與正則表達式生成器服務器110(或正則表達式生成器)通信，并與用戶界面交互以檢索和顯示表格數(shù)據(jù)，并基于經(jīng)由用戶界面對輸入數(shù)據(jù)(例如，示例)的選擇來生成正則表達式。在一些實施例中，客戶端設備120可以經(jīng)由客戶端web瀏覽器121和/或客戶端側正則表達式應用122(例如，接收/消費由服務器110生成的正則表達式的客戶端應用)與正則表達式生成器110通信。在正則表達式生成器110內(nèi)，來自客戶端設備120的請求可以在網(wǎng)絡接口處通過各種通信網(wǎng)絡被接收，并由諸如RESTAPI112的應用編程接口(API)來處理。具有正則表達式生成器110的用戶界面數(shù)據(jù)模型生成器114組件可以提供服務器側編程組件和邏輯，以生成和呈現(xiàn)本文描述的各種用戶界面特征。這樣的特征可以包括以下功能性：允許用戶從數(shù)據(jù)存儲庫130檢索和顯示表格數(shù)據(jù)，選擇輸入數(shù)據(jù)示例以啟動正則表達式的生成，以及基于所生成的正則表達式修改和/或提取數(shù)據(jù)。在該示例中，正則表達式生成器組件116可以被實現(xiàn)為生成正則表達式，包括將輸入字符序列轉換成正則表達式代碼和/或跨度，對輸入數(shù)據(jù)執(zhí)行算法(例如，LCS算法)以及生成/簡化正則表達式。由正則表達式生成器116生成的正則表達式可以由REST服務112傳輸?shù)娇蛻舳嗽O備120,在客戶端設備120中，客戶端瀏覽器121(或相應的客戶端應用組件122)上的Javascript代碼然后可以針對在瀏覽器中呈現(xiàn)的電子表格列中的每個單元格應用正則表達式。在其他情況下，可以在服務器側實現(xiàn)單獨的正則表達式引擎組件，以將生成的正則表達式與用戶界面上顯示的表格數(shù)據(jù)和/或存儲在數(shù)據(jù)存儲庫130中的其他數(shù)據(jù)進行比較，以便標識服務器側上的匹配數(shù)據(jù)/不匹配數(shù)據(jù)。在各種實施例中，匹配/非匹配數(shù)據(jù)可以在用戶界面內(nèi)被自動選擇(例如，突出顯示),并且可以被選擇用于提取、修改、刪除等?；谡齽t表達式的生成，經(jīng)由用戶界面提取或修改的任何數(shù)據(jù)可以被存儲在一個或多個數(shù)據(jù)存儲庫130中。此外，在一些實施例中，所生成的正則表達式(和/或LCS算法的相應輸入)可以存儲在正則表達式庫135中以供將來檢索和使用。在一些實施例中，所生成的正則表達210,246號中更詳細地描述的(其通過引用合并于此以用于所有目的),這樣的轉換腳本可以包括可由一個或多個處理單元執(zhí)行以轉換接收數(shù)據(jù)的程序、代碼或指令。變換腳本動作[0048]圖2是根據(jù)本文描述的一個或多個實施例，示出基于經(jīng)由用戶界面接收的輸入來生成正則表達式的過程的流程圖。在步驟201中，正則表達式生成器110可以從客戶端設備120接收訪問正則表達式生成器用戶界面并經(jīng)由該用戶界面查看特定數(shù)據(jù)的請求?？梢越?jīng)由RESTAPI112和/或web服務器、認證服務器等接收步驟201中的請求，并且可以解析和認證用戶的請求。例如，企業(yè)或組織內(nèi)的用戶可以訪問正則表達式生成器110以分析和/或修改交易數(shù)據(jù)、客戶數(shù)據(jù)、績效數(shù)據(jù)、預測數(shù)據(jù)和/或可以存儲在組織的數(shù)據(jù)存儲庫130中的任何其他類別的數(shù)據(jù)。在步驟202中，正則表達式生成器110可以經(jīng)由支持基于所選輸入數(shù)據(jù)生成正則表達式的用戶界面來檢索和顯示所請求的數(shù)據(jù)。下面詳細描述這樣的用戶界面的各種實施例和示例。[0049]在步驟203中，用戶可以從正則表達式生成器110提供的，用戶界面中顯示的數(shù)據(jù)中選擇一個或多個輸入字符序列。在一些實施例中，數(shù)據(jù)可以在用戶界面內(nèi)以表格形式顯示，包括具有特定數(shù)據(jù)類型和/或數(shù)據(jù)類別的標簽化列。在這種情況下，在步驟203中對輸入數(shù)據(jù)的選擇可以對應于用戶選擇數(shù)據(jù)單元格，或者選擇(例如，突出顯示)數(shù)據(jù)單元格內(nèi)的單個文本片段。然而，在其他實施例中，正則表達式生成器110可以支持經(jīng)由用戶界面檢索和顯示半結構化和非結構化數(shù)據(jù)，并且用戶可以通過從半結構化或非結構化數(shù)據(jù)中選擇字符序列來選擇用于正則表達式生成的輸入數(shù)據(jù)。如下面在示例中描述的，用戶從顯示的表格數(shù)據(jù)中選擇輸入字符序列僅是一個示例用例。在其他示例中，用戶(例如，軟件開發(fā)人員或高級用戶可能試圖針對Linux命令行工具grep、sed或awk等編寫正則表達式)可以從零開始輸入示例，而不是從電子表格中摘取它們。[0050]在步驟204中，正則表達式生成器110可以基于用戶在步驟203中選擇的輸入數(shù)據(jù)來生成一個或多個正則表達式。在步驟205中，正則表達式生成器110可以更新用戶界面，例如，以顯示所生成的正則表達式和/或突出顯示所顯示的數(shù)據(jù)內(nèi)的匹配/不匹配數(shù)據(jù)。在步驟206(在一些實施例中可以是可選的)中，用戶界面可以支持允許用戶基于所生成的正則表達式修改底層數(shù)據(jù)的功能。例如，用戶界面可以支持如下特征：允許用戶基于這些字段是否與正則表達式匹配來從表格數(shù)據(jù)中過濾、修改、刪除或提取特定數(shù)據(jù)字段。過濾或修改數(shù)據(jù)可以包括修改存儲在存儲庫130中的底層數(shù)據(jù)，并且在某些情況下，所提取的數(shù)據(jù)可以作為新列和/或新表格被存儲在存儲庫130中。[0051]盡管這些步驟示出了與正則表達式生成器110的用戶界面的示例性用戶交互的一般和高級概述，但是在其他實施例中可以支持各種附加特征和功能。例如，在一些實施例中，正則表達式代碼(或類別代碼)可以與該代碼的最小出現(xiàn)次數(shù)相關聯(lián)。附加地或備選地，正則表達式代碼可以與代碼的最大出現(xiàn)次數(shù)相關聯(lián)。作為示例，正則表達式代碼的集合可以包括代碼L<0,1>,以指示LCS的特定部分包括字母至少零次且至多一次。[0052]此外，在一些實施例中，輸入數(shù)據(jù)可以包括三個或更多個字符序列。在這樣的實施例中，可以使用技術來確定對三個或更多個字符序列執(zhí)行LCS算法的順序，從而可以以高性能方式生成所得到的正則表達式，以避免由三個或更多個輸入字符序列導致的運行時間的指數(shù)增加。相反，正則表達式生成器110可以一次對兩個字符序列執(zhí)行LCS算法，并且可以基于圖來確定用于選擇這對字符序列的順序。例如，全連接圖可以指示應針對序列1和序列3的第二執(zhí)行，以此類推。該圖可以是全連接圖，具有表示字符序列的節(jié)點，以及連接節(jié)點的邊以表示由所連接的節(jié)點共享的LCS的長度。圖中的每個節(jié)點可以連接到圖中的每個其他節(jié)點，并且可以通過執(zhí)行針對圖的最小生成樹的深度優(yōu)先遍歷來確定用于選擇字符序列的順序。[0053]在其他實施例中，可以經(jīng)由用戶界面以多種不同方式提供輸入數(shù)據(jù)。例如，輸入數(shù)據(jù)可以指示在字符集的第二用戶選擇內(nèi)對一個或多個字符的第一用戶選擇。例如，用戶可以突出顯示先前突出顯示的字符集合中的字符。因此，第二用戶選擇可以提供針對第一用戶選擇的上下文，這可以使輸入數(shù)據(jù)能夠更有針對性地被提供給正則表達式生成器110。在一些實施例中，正則表達式生成器110可以響應于每個用戶選擇近乎實時地生成并顯示正則表達式。例如，當用戶突出顯示第一字符范圍時，正則表達式生成器110可以顯示表示第一字符范圍的正則表達式。然后，當用戶突出顯示第一字符范圍內(nèi)的第二字符范圍時，正則表達式生成器110可以更新所顯示的正則表達式。[0054]另外，在一些實施例中，正則表達式生成器110可以基于包括肯定和否定示例的輸入來生成正則表達式。如上所述，肯定示例可以指要被正則表達式包含的字符序列，而否定示例可以指將不被正則表達式包含的字符序列。在這種情況下，正則表達式生成器110可以在特定位置標識將肯定示例和否定示例區(qū)分開的一個或多個字符的最短子序列。然后，最短子序列可以硬編碼在正則表達式生成器110生成的正則表達式內(nèi)。在各種示例中，最短子序列可以包括在否定示例內(nèi)的前綴/后綴部分或中間跨度內(nèi)。[0055]下面描述根據(jù)某些實施例的用于自動生成正則表達式的其他示例。這些示例可以對應于圖2中的通用技術的各種具體可能的實現(xiàn)，并且可以用由相應系統(tǒng)、硬件或其組合的件可以存儲在非易失性存儲介質上(例如，存儲設備上)。下面描述的其他示例意在是說明性的和非限制性的。雖然這些示例描述了以特定序列或順序發(fā)生的各種處理步驟，但這并不意圖是限制性。在某些備選實施例中，這些步驟可以按某種不同的順序執(zhí)行，或者某些步驟也可以并行執(zhí)行。[0056]在一些示例中，經(jīng)由用戶界面接收的用戶輸入(例如，步驟203)可以包括正則表達式輸出要匹配的一個或多個“肯定示例”,以及正則表達式輸出不匹配的零個或多個“否定示例”。可選地，可以突出顯示一個或多個肯定示例以選擇特定范圍(或子序列)的字符。在一些情況下，在步驟204中，可以將經(jīng)由用戶界面接收的肯定示例轉換為正則表達式代碼(例如，諸如Unicode類別代碼的字符類別代碼)的跨度。對于每個肯定示例，可以生成一系列跨度。在一些實施例中可以創(chuàng)建圖，其中每個頂點對應于跨度的序列之一，并且邊權重等于在對應于邊的端點的這兩個跨度序列上執(zhí)行的LCS算法的輸出的長度?？梢葬槍υ搱D確定最小生成樹。例如，在一些實施例中可以使用Prim算法來獲得最小生成樹?？梢栽谧钚∩蓸渖蠄?zhí)行深度優(yōu)先遍歷以確定遍歷順序，之后可以在遍歷的前兩個元素上執(zhí)行LCS算法。然后，通過對前一次LCS迭代的輸出和下一次當前遍歷元素再次執(zhí)行LCS算法，可以一個接一個地將遍歷的每個附加元素按順序合并到當前LCS輸出中。然后，可以將LCS算法的最終輸出(其可以是跨度序列)轉換為正則表達式。在一些實施例中，轉換可以是一對一轉換，而本文描述的某些可選修飾可能不對應于一對一轉換。最后，在步驟203中，可以針對經(jīng)由用戶界面接收的所有肯定和否定示例來測試所得到的正則表達式。如果任何測試失敗，則可以使用所有失敗的肯定示例和任何否定示例重復上述過程。[0057]I.在正則表達式代碼上使用最長通用子序列算法的正則表達式生成[0058]如上所述，本文描述的某些方面涉及基于計算由對應于輸入數(shù)據(jù)的不同正則表達式代碼集合共享的最長通用子序列(LCS)來生成正則表達式。[0059]圖3是根據(jù)本文描述的一個或多個實施例，示出在正則表達式代碼集上使用LCS算法生成正則表達式的過程的流程圖。在步驟301中，正則表達式生成器110可以接收一個或多個字符序列作為輸入數(shù)據(jù)。如上所述，在一些示例中，輸入數(shù)據(jù)可以對應于從用戶界面中顯示的表格數(shù)據(jù)中選擇的肯定示例數(shù)據(jù)，但應該理解，在一些實施例中，用戶界面是可選的，并且在各種示例中，輸入數(shù)據(jù)可以對應于從任何其他通信信道(例如，非用戶界面)接收的任何字符序列。[0060]在步驟302中，可以將在步驟301中接收到的每個字符序列轉換為相應的正則表達式代碼。在各種實施例中，正則表達式代碼可以是Loogle碼、Unicode類別代碼或表示正則“LLLZN”。在一些實施例中，正則表達式代碼可以是基于https://www.regular-碼L可以代表字母，代碼N可以代表數(shù)字，代碼Z可以代表以代表標點符號，等等。例如，代碼L可以對應于Unicode\p{L},而代碼N可以對應于[0061]在步驟303中，可以根據(jù)在步驟302中生成的正則表達式代碼集合確定最長通用子序列。在一些實施例中，可以使用兩個正則表達式代碼集合作為輸入來執(zhí)行LCS算法?？梢栽诓煌膶嵤├惺褂肔CS算法的執(zhí)行的各種不同特征(例如，處理方向、錨定、推送空間、合并低基數(shù)跨度、對齊通用令牌等)。在步驟304中，可以基于LCS算法的輸出來生成正則表達式。在一些情況下，步驟304可以包括捕獲正則表達式代碼中的LCS算法的輸出，并將正則表達式代碼轉換為正則表達式。在步驟305中，可以例如通過經(jīng)由用戶界面向用戶顯示正則表達式來簡化并輸出正則表達式。[0062]圖4是用于基于兩個字符序列示例，在正則表達式代碼集合上使用最長通用子序列(LCS)算法來生成正則表達式的示例圖。因此，圖4示出了應用上面在圖3中討論的處理的成的。該示例中的每個序列可以被轉換成相應的正則表達式代碼集合。因此，iPhone5可以碼作為輸入提供給LCS算法，該算法確定兩個IREC(或類別代碼)都包括六個L和一個Z。從LCS中排除的類別代碼可以表示為可選的和/或備選的。因此，包含兩個字符序列的正則表達式可以表示為：\pL{6}\pZ\pN?\pL?。在本示例中，正則表達式包括Unicode類別代碼(例問號指示末尾的數(shù)字/字母是可選的。最后，正則表達式生成器可以執(zhí)行簡化過程，簡化過程期間通過將通用文本片段“iphone”重新插入回最終正則表達式中，替換正則表達式的更[0063]如本示例所示，由正則表達式生成器110接收的輸入串可以被轉換成表示正則表達式廣義類別(也可以被稱為“類別代碼”)的“正則表達式代碼”,并且LCS算法可以在這些正則表達式代碼上運行。在一些實施例中，Unicode類別代碼可以用于正則表達式代碼。例代表標點符號等)。圖3和圖4所示的這種方法可以稱為間接方法。然而以使用直接方法，其中LCS算法直接在作為輸入接收的字符序列上運行。[0064]在一些實施例中，間接方法可以提供附加的技術優(yōu)勢，因為它不需要大量的訓練數(shù)據(jù)，并且可以用相對較少的輸入示例生成有效的正則表達式。這是因為間接方法采用啟發(fā)式來減少正則表達式生成中的不確定性，并消除潛在的假陽性和假陰性。例如，在基于輸入串“May3”和“Apr4”生成正則表達式時，直接方法可能每個月至少需要一個示例來生成與日期模式匹配的有效正則表達式。僅依靠這兩個示例，直接方法可能會生成“[AM][ap][yr][13]1?”的regex。相反，基于Unicode廣義類別，間接方法可以生成更有效的正則表達式“\pL{3}\d{1,2}”。此外，如上所述，本文描述的技術優(yōu)勢之一包括使用非常少的輸入數(shù)據(jù)(甚至潛在地從單個示例)高效地生成正則表達式。例如，關于從單個示例“am”生成正則表達式，啟發(fā)式可以確定針對正則表達式生成“am”還是“\pL\pL”。兩者都可論證是正確的，但因此編程的啟發(fā)式可以實現(xiàn)用戶偏好和/或標準，以確定如何生成最佳正則表達式(例{3}\d{1,2}”,以使其更具人類可讀性。這在一些實施例中可能是有益的，例如當向可能不熟悉針對正則表達式的Unicode表達式的非復雜性正則表達式用戶輸出時。順序且相等的正則表達式代碼轉換成跨度數(shù)據(jù)結構(其也可以被稱為跨度)。在一些情況下，跨度可以包括單個正則表達式代碼(例如，Unicode廣義類別代碼)的表示，以及重復計數(shù)范圍(例如，最小數(shù)目和/或最大數(shù)目)。從正則表達式代碼到跨度的轉換可以有助于下面描述的一些不同的附加特征，諸如識別備選(例如，析取),并且還可以有助于合并相鄰可選跨度以進一步簡化所生成的正則表達式。[0067]如上所述，LCS算法可以被配置為存儲和保留輸入字符序列內(nèi)的底層文本片段，其配給該跨度的類別代碼的文本片段，這樣的實施例可以允許將文字文本(例如，am和pm)直接包括在所生成的正則表達式中，這可以減少假陽性并使正則表達式輸出更具人類可讀性。[0068]III.在正則表達式代碼組合上使用最長通用子序列算法生成正則表達式[0069]本文描述的附加方面涉及基于包括三個或更多個字符串(例如，三個或更多個單獨的字符序列)的輸入數(shù)據(jù)來生成正則表達式。當三個或更多個字符串被標識為輸入數(shù)據(jù)時，正則表達式生成器110可以使用性能優(yōu)化特征，其中針對LCS算法執(zhí)行的序列確定最佳順序。如下所述，針對多于兩個字符串的性能優(yōu)化特征可以包括構建圖，該圖具有對應于每個字符串的頂點，以及可以基于每個字符串和每隔一個字符串之間的LCS輸出的大小的邊長度/權重。然后，可以使用這些邊權重來導出最小生成樹，并且可以執(zhí)行深度優(yōu)先遍歷以[0070]圖5是示出在更大的正則表達式代碼集合(例如，三個或更多個字符序列)上使用最長通用子序列(LCS)算法生成正則表達式的過程的流程圖。因此，本示例中的步驟502-505可以對應于上面在圖3中討論的步驟303。然而，由于本示例涉及基于三個或更多個輸入字符序列生成正則表達式，因此可以多次執(zhí)行LCS算法。例如，為了避免三個或更多個輸入串的運行時間的指數(shù)增加，可以多次執(zhí)行LCS算法，其中每次執(zhí)行僅在兩個輸入串上執(zhí)行。例如，正則表達式生成器110可以對兩個字符串(例如，兩個輸入字符序列或兩個轉換的正則表達式代碼)執(zhí)行LCS算法的初始執(zhí)行，然后可以對第一LCS算法的輸出和第三字符串執(zhí)行LCS算法的第二執(zhí)行，然后可以對第二LCS算法的輸出和第四字符串執(zhí)行LCS算法的第三[0071]為了改進和/或優(yōu)化這種實施例的性能，可能希望確定針對輸入字符串(例如，輸入字符序列或正則表達式代碼)的最佳順序以執(zhí)行LCS算法序列。例如，獲取輸入字符串的良好順序可能會影響所生成的正則表達式的可讀性，例如通過最小化可選跨度的數(shù)量。為了保持所生成的regex的簡明性，LCS到當前regex的附加字符串應優(yōu)選地已與當前regex(對已經(jīng)看到的字符串進行LCS得到的中間結果)有些類似。[0072]因此，在步驟501中，將多個(例如，3個或更多個)輸入字符序列轉換為正則表達式代碼。在步驟502中，確定使用LCS算法處理正則表達式代碼的順序。下面參照圖7更詳細地討論步驟502中的順序確定。在步驟503中，或者選擇所確定順序的前兩個正則表達式代碼(對于步驟503的第一次迭代),或者選擇所確定順序的下一個正則表達式代碼(對于步驟503的后續(xù)迭代)。在步驟504中，對與正則表達式代碼格式對應的兩個輸入字符串執(zhí)行LCS算法。對于步驟504的第一次迭代，對所確定順序的前兩個正則表達式代碼執(zhí)行LCS算法，而對于步驟504的后續(xù)迭代，對所確定順序的下一個正則表達式代碼和前次LCS算法的輸出(也可以是相同格式的正則表達式代碼)執(zhí)行LCS算法。在步驟505中，正則表達式生成器110確定所確定的順序中是否存在尚未作為輸入提供給LCS算法的附加正則表達式代碼。如果是，則該過程返回到步驟503,用于LCS算法的另一次執(zhí)行。如果不是，則在步驟506中，基于LCS算法的最后一次執(zhí)行的輸出生成正則表達式。[0073]圖6是基于五個輸入字符序列示例生成正則表達式的示例圖。在該示例中，每個輸入字符序列被轉換為正則表達式代碼，然后基于正則表達式代碼的確定順序重復執(zhí)行LCS算法。因此，圖6示出了應用上述圖5中討論的過程的一個示例，在該示例中，五個正則表達式代碼的確定順序是代碼#1到代碼#5,并且每個代碼以所確定順序輸入到LCS算法以生成正則表達式輸出。最終正則表達式輸出(RegEx#4)對應于基于所有五個輸入字符序列生成的最終正則表達式。[0074]圖7是示出用于在更大的正則表達式代碼集合(例如，三個或更多)上確定最長通用子序列(LCS)算法的執(zhí)行順序的過程的流程圖。因此，如本示例所示，步驟701-704可以對應于上面討論的步驟502中的順序確定。在步驟701中，可以在對應于輸入數(shù)據(jù)的每個唯一于k個輸入數(shù)據(jù)，這可以表示要運行LCS算法的所有(k(k-1))/2個可能的字符串配對，或者在一些實施例中表示k(k-1)個。例如，如果接收到k=3個輸入字符序列，則在步驟701中可以運行LCS算法三次；如果接收到k=4個輸入字符序列，則可以在步驟701中運行LCS算法六次；如果接收到k=5個輸入字符序列，則可以在步驟701中運行LCS算法10次，以此類推。在步驟702中，可以由表示字符串的k個節(jié)點構成全連接圖，其中(k(k-1))/2條邊的邊權重是兩個節(jié)點之間的原始LCS輸出的長度。在步驟703中，可以從步驟702中的完全連接圖中導出最小生成樹。在步驟704中，可以對最小生成樹執(zhí)行深度優(yōu)先遍歷。該遍歷的輸出可以對應于正則表達式代碼將被輸入到LCS算法執(zhí)行序列中的順序。[0075]簡要參考圖8A和8B,圖5中示出了基于接收到的k=5個輸入字符序列生成的全連接圖的示例，并且在圖8B中示出了針對全連接圖的最小生成樹表示。[0076]在一些實施例中，圖5-8B中描述的方法可以提供關于性能的附加技術優(yōu)勢。例如，LCS算法的某些傳統(tǒng)實現(xiàn)可以表現(xiàn)出0(n2)的運行時性能，其中n是字符串的長度。將這種實現(xiàn)擴展到k個字符串而不是僅2個，可能會導致指數(shù)運行時間性能0(nk),因為可能需要LCS算法來搜索k維空間。LCS算法的這種傳統(tǒng)實現(xiàn)可能性能不高或不足以適合實時在線用戶體驗。[0077]如上所述，LCS算法可以被執(zhí)行(k(k-1))/2次，其中有時副本與之前已經(jīng)看到的完全相同，因為LCS算法可以在來自用戶的原始輸入示例已經(jīng)被轉換成regex類別代碼時。因此，可以在某些情況下實現(xiàn)記憶性，其中可以使用高速緩存來將先前看到的LCS問題映射到先前工作的LCS解決方案。[0078]IV.基于肯定和否定模式匹配示例的正則表達式生成[0079]本文描述的附加方面涉及基于與肯定示例和否定示例兩者相對應的輸入數(shù)據(jù)生成正則表達式。如上所述，肯定示例可以指被指定為應與正則表達式生成器將生成的正則表達式匹配的示例字符串的輸入數(shù)據(jù)字符序列。相反，否定示例可以指被指定為不應與正則表達式生成器將生成的正則表達式匹配的示例字符串的輸入數(shù)據(jù)字符序列。如下所述，在一些實施例中，正則表達式生成器110可以被配置為標識將肯定示例和否定示例區(qū)分開的位置和該位置處的最短字符子序列。然后，最短子序列可以被硬編碼到所生成的正則表達式中，使得肯定示例將與正則表達式匹配，而否定示例將被正則表達式排除(例如，將不匹配)。[0080]圖9是示出基于肯定和否定字符序列示例生成正則表達式的過程的流程圖。在步驟901中，正則表達式生成器110可以接收對應于肯定示例的一個或多個輸入數(shù)據(jù)字符序列。在步驟902中，正則表達式生成器110可以基于接收到的肯定示例來生成正則表達式。因此，步驟901-902可以包括上面討論的圖3或圖5中執(zhí)行的一些或全部步驟，以基于輸入數(shù)據(jù)字符序列生成正則表達式。[0081]在步驟903中，正則表達式生成器110可以接收與否定示例相對應的一個附加輸入數(shù)據(jù)字符序列。因此，特定地指定否定示例，使得與在步驟902中生成的正則表達式不匹配。在一些實施例中，可以首先對照在步驟902中生成的正則表達式來測試在步驟903中接收到的否定示例，并且如果確定該否定示例與正則表達式不匹配，則不采取進一步的動作。然而，在該示例中，可以假設在步驟903中接收的否定示例中的至少一個與在步驟902中生成的正則表達式匹配。因此，在步驟904中，可以在步驟902中生成的正則表達式內(nèi)確定消歧位置。在一些實施例中，消歧位置可以被選擇為前綴位置(例如，在正則表達式的開頭)或后綴位置(例如，在正則表達式的末尾)。例如，正則表達式生成器110可以確定在前綴處需要的第一數(shù)量的字符以將肯定示例和否定示例區(qū)分開，以及在后綴處需要的第二數(shù)量的字符以將肯定示例和否定示例區(qū)分開。正則表達式生成器110然后可以基于所需的最短數(shù)量的替換字符來選擇后綴或前綴。在某些情況下，出于可讀性的目的，使用前綴作為消歧位置可能是優(yōu)選的(例如，被加重)。在其他示例中，消歧位置可以是不對應于正則表達式的前綴或后綴的中間跨度位置。[0082]在步驟905中，正則表達式生成器110可以確定定制字符類的替換序列，當在所確定的位置處將其插入到正則表達式中時，該替換序列可以區(qū)分肯定示例和否定示例。在一些實施例中，正則表達式生成器110在步驟905中可以從與消歧位置(或替換位置)相對應的肯定和否定示例中的每一個檢索文本片段，然后使用該文本片段來確定將用作區(qū)分肯定示例和否定示例的替換序列的鑒別符。另外，在步驟905中確定的鑒別符替換序列可以包括定制字符類的多個不同的替換序列，其可以在正則表達式內(nèi)的相同位置或不同位置被替換。[0083]如上所述，在一些情況下，可以結合步驟904中的消歧位置(或替換位置)的確定來執(zhí)行步驟905中的替換序列的確定。例如，正則表達式生成器110可以確定在第一可能的替換位置可以區(qū)分肯定和否定示例的一個或多個替換序列。正則表達式生成器110還可以確定在第二不同的可能替換位置可以區(qū)分肯定和否定示例的一個或多個其他替換序列。在該示例中，當在不同的可能替換位置和相應的替換序列之間進行選擇時，正則表達式生成器110可以應用啟發(fā)式公式以基于替換位置的字符大小以及相應替換序列的數(shù)量和/或大小中的一個或多個來執(zhí)行選擇。最后，在步驟906中，可以通過將一個或多個確定的替換序列插入到所確定位置以替換正則表達式的先前部分來修改正則表達式。在一些情況下，在步驟906中修改正則表達式之后，可以對照修改后的正則表達式來測試肯定示例和/或否定示例，以確認肯定示例匹配并且否定示例不匹配正則表達式。[0084]圖10A和10B是示出基于肯定和否定字符序列示例生成正則表達式的示例用戶界面屏幕。因此，圖10A和10B中示出的示例可以對應于在執(zhí)行上面討論的圖9的過程期間顯示的用戶界面。在圖10A中，用戶提供數(shù)據(jù)輸入字符序列1001的三個肯定示例，并且正則表達式生成器110生成與每個肯定示例匹配的正則表達式1002。然后，在圖4B中，用戶提供一個否定示例1004,并且正則表達式生成器110生成修改的正則表達式1005,其基于肯定示例1003和否定示例1004的兩個當前集合。成器110可以標識區(qū)分肯定示例和否定示例的鑒別符或一個或多個字符的最短子序列。所選擇的鑒別符可以是最短序列(例如，以類別代碼表示),并且既可以是肯定的也可以是否某些情況下，該算法以生成否定回溯來正確鑒別。例如，(?<!Av)[A-Za-z]+將排除分肯定示例和否定示例(例如，假設目標是匹配商務電話號碼的正則表達式),可以針對正換),而不是通過使用更大數(shù)量的字符串片段來消歧(例如，從而是要替換的字符串片段數(shù)[0097]一旦確定了前綴/后綴和k(要消歧的字符數(shù)),則正則表達式生成器110仍然可以[0099]如果usePermissive大于零，則通過生成允許從肯定示例中逐個(針對每個字符位置)獲取字符的正則表達式來允許看起來像肯定示例的內(nèi)容通過。在其他情況下，正則表達式生成器110可以通過生成不允許從否定示例中逐個(針對每個字符位置)獲取字符的正則表達式來采取不允許看起來像否定示例的內(nèi)容的方法。[0100]作為另一示例，針對肯定示例8am和否定示例9pm生成的正則表達式可以是\d[^p]m。這使用插入符號語法。在一些情況下，正則表達式生成器110可以被配置為偏愛較短的正則表達式，其不僅對用戶更具可讀性，而且更有可能是正確的。理由是，頻繁出現(xiàn)的字符在未來更有可能再次出現(xiàn)，因此應該把重點放在頻繁出現(xiàn)的字符上。如果唯一字符|F。|較少(唯一字符較少，因為出現(xiàn)的字符出現(xiàn)的頻率更高),則這在啟發(fā)式中的獎勵是將其放在分[0101]再次參考上面的usePermissive示例啟發(fā)式方法，如果只有一個來自用戶的肯定示例，則確定一個唯一的肯定詞綴并不是什么了不起的事情。因此，在該啟發(fā)式方法中，低|E|通過將其置于分子來懲罰(即，在該啟發(fā)式方法中獎勵高|E|)。[0102]另外，在一些實施例中，否定示例可以基于回溯和/或前瞻。例如，用戶可以提供以排除帶區(qū)號的電話號碼。[0103]在某些情況下，否定示例也可以基于可選跨度。例如，用戶可以提供“ab”和“a2b”的肯定示例以及“a3b”的否定示例。在這種情況下，示例實現(xiàn)可能會失敗，因為它可能嘗試僅基于所需的跨度進行區(qū)分，并且“2”數(shù)字在可選跨度中。在本示例中生成的正則表達式與所有肯定示例匹配(正確),也與一個或多個否定示例匹配(錯誤)的情況。在這種情況下，可以向用戶警告該故障，并且可以經(jīng)由用戶界面向用戶提供手動修復所生成的正則表達式和/或移除一些否定示例的選項。[0104]V.用于正則表達式生成的用戶界面[0105]本文描述的附加方面包括圖形用戶界面內(nèi)與正則表達式生成相關的若干不同特征和功能。如下所述，這些特征中的某些特征可以包括用于用戶選擇和突出顯示肯定和否定示例、針對肯定和否定示例的顏色編碼、以及數(shù)據(jù)單元格內(nèi)的多個重疊/嵌套突出顯示的各種選項。[0106]圖11是示出基于在用戶界面內(nèi)接收的用戶數(shù)據(jù)選擇來生成正則表達式的過程的流程圖。圖11中的示例過程可以對應于基于輸入數(shù)據(jù)字符序列生成正則表達式的任何前面討論的示例。然而，圖11描述了關于可以在客戶端設備120上生成和顯示的用戶界面的過程。在步驟1101中，響應于來自用戶經(jīng)由用戶界面的請求，正則表達式生成器110可以(例如，從數(shù)據(jù)存儲庫130)檢索數(shù)據(jù)，并在圖形用戶界面內(nèi)以表格形式呈現(xiàn)/顯示數(shù)據(jù)。盡管在這個示例中使用了表格數(shù)據(jù)，但是應該理解，在其他示例中不需要使用或顯示表格數(shù)據(jù)。例如，在某些情況下，用戶可以直接鍵入原始數(shù)據(jù)(而不是從用戶界面選擇數(shù)據(jù))。另外，當經(jīng)由用戶界面呈現(xiàn)數(shù)據(jù)時，數(shù)據(jù)不需要以表格形式，而可以是非結構化數(shù)據(jù)(例如，文檔)或半結構化(例如，諸如推文或帖子的非格式化/非結構化數(shù)據(jù)項的電子表格)。在各種示例中，表格數(shù)據(jù)可以對應于交易數(shù)據(jù)、客戶數(shù)據(jù)、績效數(shù)據(jù)、預測數(shù)據(jù)和/或可以存儲在企業(yè)或其他組織的數(shù)據(jù)存儲庫130中的任何其他類別的數(shù)據(jù)。在步驟1102中，可以經(jīng)由用戶界面接收用戶對輸入數(shù)據(jù)的選擇。例如，所選擇的輸入數(shù)據(jù)可以對應于由用戶選擇的整個數(shù)據(jù)單元，或者數(shù)據(jù)單元內(nèi)的字符的子序列。在步驟1103中，正則表達式生成器110可以基于在步驟1102中接收的輸入數(shù)據(jù)(例如，數(shù)據(jù)單元或其部分)來生成正則表達式。在步驟1104中，可以響應于正則表達式的生成來更新用戶界面。在一些情況下，可以簡單地更新用戶界面以向用戶顯示所生成的正則表達式，而在其他情況下，用戶界面可以按照下面討論的各種其他方式來更新。如本示例所示，用戶可以經(jīng)由用戶界面選擇多個不同的輸入數(shù)據(jù)字符序列，并且響應于接收到的每個新的輸入數(shù)據(jù)，正則表達式生成器110可以生成包含字符序列的第一和第二(肯定)示例的更新的正則表達式。然后，當用戶突出顯示第三字符序列時(例如，在兩個字符序列之外，或者在第一或第二字符序列內(nèi)),正則表達式生成器110可以再次更新正則表達式，依此類推。在一些實施例中，正則表達式生成器110可以實時(或接近實時)執(zhí)行該算法，使得響應于用戶進行的每一個新的擊鍵或每一個新的突出顯示部分來生成全新的正則表達式。[0107]因此，如圖11所示，響應于用戶經(jīng)由用戶界面對字符序列的選擇，正則表達式生成器110可以生成并顯示正則表達式。例如，當用戶突出顯示第一字符序列時，正則表達式生成器可以生成并顯示表示第一字符序列的正則表達式。當用戶突出顯示第二字符序列時，正則表達式生成器可以生成包含第一和第二字符序列的更新的正則表達式。然后，當用戶突出顯示第三字符序列(例如，在第一或第二序列內(nèi))時，正則表達式生成器可以再次更新[0108]圖12是示出經(jīng)由在用戶界面內(nèi)接收的用戶數(shù)據(jù)選擇，基于捕獲組來生成正則表達式和提取數(shù)據(jù)的過程的另一流程圖。在步驟1201中，如上文在步驟1101中所討論的，正則表達式生成器110可以(例如，從數(shù)據(jù)存儲庫130)檢索數(shù)據(jù)，并在圖形用戶界面內(nèi)以表格形式呈現(xiàn)/顯示數(shù)據(jù)。在步驟1202中，正則表達式生成器110可以接收對特定數(shù)據(jù)單元格內(nèi)的文本片段的用戶突出顯示的選擇。在步驟1203中，正則表達式生成器110可以基于所選數(shù)據(jù)單元格的肯定示例來生成正則表達式，并且在步驟1204中可以基于單元格內(nèi)突出顯示的文本片段來創(chuàng)建正則表達式捕獲組。在步驟1205中，正則表達式生成器110可以確定所顯示的表格數(shù)據(jù)中與所生成的正則表達式相匹配的一個或多個附加單元格，并且在步驟1206中，可以提取與所生成的正則表達式相匹配的附加單元格中的相應文本片段。[0109]因此，除了提供肯定示例之外，用戶還可以選擇(例如，經(jīng)由鼠標文本突出顯示)任何所選肯定示例內(nèi)的文本片段。作為響應，正則表達式生成器110可以創(chuàng)建正則表達式捕獲組以從該示例中提取該文本片段以及從該正則表達式應用到的文本中的所有其他匹配中提取相應片段。從匹配的數(shù)據(jù)單元中提取文本片段還可以包括刪除和修改，并且在某些情況下可以用于在半結構化或非結構化文本的現(xiàn)有列之外創(chuàng)建新的數(shù)據(jù)列。[0110]使用用戶選擇肯定數(shù)據(jù)示例的示例，并且如果用戶突出顯示年份，則正則表達式生成器110可以生成正則表達式(?:[A-Z]{3}\s+\d\d,\s+|\d\d/\d\d)(\d\d\d\d)。如本示例所示，正則表達式生成器110已經(jīng)在年份周圍放置了圓括號，并且還通過使用?:正則表達式語法將圍繞月和日(用于備選)的舊圓括號轉換為“非捕獲”組。在一些實施例中，可能需要提取/捕獲組落在跨度邊界上，并且在這樣的實施例中，正則表達式生成器110可以將突出顯示的字符范圍作為輸入并將其擴展以包含最近的錨跨度邊界。然而，在其他示例中，用戶界面可以支持中間跨度提取/捕獲。[0111]在一些實施例中，用戶界面可以支持來自用戶的包括對第二字符序列內(nèi)的第一字符序列的選擇的輸入數(shù)據(jù)。例如，用戶可以突出顯示較大的先前突出顯示的字符序列內(nèi)的一個或多個字符，并且第二用戶選擇可以針對較大的第一用戶選擇提供上下文。這樣的實施例可以使輸入數(shù)據(jù)能夠更有針對性地提供給正則表達式生成器110。[0112]此外，在一些示例中，可以響應于用戶在用戶界面進行選擇(例如，突出顯示文本)來發(fā)起操作并且可以打開對話框。在一些情況下，該對話框可以是非模型對話框，例如不阻止用戶與主屏幕交互的浮動工具箱窗口。取決于用戶正在執(zhí)行的主要操作，該對話框還可以在外觀和/或功能上改變。因此，在這種情況下，用戶不需要在突出顯示所選文本之后搜于生成正則表達式的用戶界面可以包括三種突出顯示模式：嵌套自動、嵌套手動和單層。在某些情況下，默認操作模式可以是將整個單元格標識為突出顯示區(qū)域，并且用戶還可以突出顯示所突出顯示單元格內(nèi)的一個或多個附加子序列。在其他模式中，可以允許用戶在表格數(shù)據(jù)顯示的數(shù)據(jù)單元格內(nèi)手動指定兩個突出顯示。在其他模式中，可以允許用戶手動指定外部突出顯示，而沒有內(nèi)部突出顯示。這些其他模式可能更適合于“半結構化”數(shù)據(jù)，例據(jù)指的是可以在用戶界面內(nèi)以表格形式顯示的數(shù)據(jù)，但是該表格內(nèi)的列由非結構化文本組[0113]在一些這樣的實施例中，用戶經(jīng)由用戶界面進行的內(nèi)部和外部選擇(例如，突出顯示)可以通過顏色編碼來區(qū)分。例如，肯定示例的外部突出顯示可以以第一文本/背景顏色組合顯示，而肯定示例的內(nèi)部突出顯示可以以不同的對比文本/背景顏色組合顯示。[0114]如上所述，用戶可以經(jīng)由選擇字符子序列來指定捕獲組的選擇。該GUI可用于經(jīng)由突出顯示(或其他指示)方便用戶選擇。圖13示出了示例，其中示出了具有表格數(shù)據(jù)顯示的示例用戶界面屏幕。在該示例中，圖13描繪了例如由用戶在列值的一個或多個所需元素上拖拽鼠標引起的列值內(nèi)的突出顯示。注意，在其中執(zhí)行用戶突出顯示的“單元格”可以表現(xiàn)出指示選擇列值的顏色改變。該顏色改變可以被解釋為響應于用戶突出顯示而自動突出顯[0115]圖14和15是示例用戶界面屏幕，示出了基于從表格顯示中選擇數(shù)據(jù)來生成正則表達式和捕獲組。在這些示例中，圖14和圖15示出了附加用戶界面窗口，其自動顯示檢測到表格數(shù)據(jù)顯示內(nèi)的用戶突出顯示1401。該窗口包括用于顯示肯定示例的字段1402、用于顯示否定示例的字段、以及用于響應于從表格數(shù)據(jù)顯示中選擇肯定示例而顯示動態(tài)(并且?guī)缀跫磿r地)生成的正則表達式的字段。在這些示例中，列值1401內(nèi)的用戶突出顯示可以等同于自動突出顯示內(nèi)的用戶突出顯示。因此，用戶突出顯示區(qū)號不僅導致用戶突出顯示的區(qū)號1401,而且還導致電話號碼的其余部分被填充在肯定示例字段1402中。在其他用戶突出顯示內(nèi)執(zhí)行用戶突出顯示。作為另一示例，用戶突出顯示可以備選地在沒有任何內(nèi)部突出顯示的情況下執(zhí)行(例如，在突出顯示的文本內(nèi)進一步突出顯示)。這些備選的示例特別適合于半結構化數(shù)據(jù)，例如包括"Tweets”或其他長字符串(例如，瀏覽器“用[0117]此外，在生成相應的正則表達式時，可以基于附加的自動突出顯示來標識與該正則表達式匹配的其他列值1402。在圖14和15所示的示例中，附加的自動突出顯示指示與所生成的正則表達式的捕獲組相匹配的這些其他列值的元素?？梢允褂门c用于用戶突出顯示的顏色不同的顏色來執(zhí)行附加的自動突出顯示。[0118]如圖