用於從非結構化描述生成結構化表示的系統和方法

2023-05-27 23:19:56 3

專利名稱：用於從非結構化描述生成結構化表示的系統和方法
技術領域：
本發明一般涉及用於結構化和形式化非結構化且不嚴密的信息的方法和系統。具體地說，它涉及用於通過來自提供指導的計算機系統的支持來獲得非結構化信息並且使其結構化和形式化的方法和系統。另外，本發明涉及一種用於通過計算機的幫助來獲得過程或任務的不嚴密描述並且使其嚴密且形式化的系統。
背景技術：
大量活動-特別是創造活動-包括工程，需要從業者製作對客戶需要的解決方案的結構化圖、文檔或規範。例如，土木工程師在設計新橋梁時可能製作設計圖和結構分析，信息技術(IT)架構師在設計IT系統以滿足新業務需要時製作需求文檔、以及設計模型，或者作曲者為電影製作配樂。在這些領域的每一個中，創造工作的結果是足以讓他人建造或照辦的、高度結構化的規範或設計。
同時，存在專用於這些領域的系統，其以這些領域的形式化或結構化概念表示信息。作為示例，IT架構師的典型工具可以表示諸如組件、接口等的IT構造，而為電影配樂的典型工具表示配樂部分、由樂器演奏的音符以及電影的時間方面。
相反，在這些活動的開始，可用信息典型地是非結構化的，並且在質量、數量和細節上是變化的，從而反映來自各種各樣的來源的信息的起源。大多數輸入來自從業者可以記錄筆記的會談和會議。其它輸入由與從業者所受的培訓不同的人或者由於其它原因使用非結構化格式而非使用創造領域中的工具來提供素材的人準備。例如，IT客戶可以在文本文檔中指定需求或業務目標。
由於在開始可用於從業者的信息的內容和格式與行業工具和產物(artifact)所要求的信息內容和格式之間的這一不匹配，因此專用於這些領域的系統經常具有有限的吸引力。例如，在音樂和IT架構領域內，研究顯示出從業者不使用領域特定工具，直至他們設計出解決方案的很多細節之後。其結果經常是低效和不準確。
而且，雖然世界中的大部分數據採用非結構化且非形式化的格式(這包括包含採用英語和其它語言的信息的文檔)，但是計算機要求，在它們可以對信息執行高級處理活動，例如使用信息執行一系列步驟，檢測信息的不一致等之前，該信息採用格式化且形式化的格式。信息的形式化表示具有可以在數學上定義的嚴密語法和語義。這允許採用形式化格式的信息被機器處理。例如，以嚴密的語義創建形式化表示對於一些信息處理活動例如查詢資料庫、創建系統的形式化模型、在數據集合上推理等是必要的。
不幸的是，形式化表示的創建對於應用這些和相關的處理活動可能是瓶頸，因為擁有與應用領域有關的詳細知識的專家經常不熟練於產生形式化表示。
存在兩個傳統的方案來嘗試解決該瓶頸。然而，這些傳統方案都是嚴重受限的。傳統地，當沒有經驗的人希望創建結構化、形式化的信息表示時，他們可能(1)尋找形式化表示法的專家來幫助他們，或者(2)試圖自己學習表示法。第一方案是嚴重受限的，這是因為如上所述，熟悉領域的、形式化表示法的專家是非常少的，並且第二方案由於學習任何特定形式化表示法的複雜性的困難而也是受限的。
存在現有的技術來嘗試解決非結構化信息的處理和管理。這些傳統的方案被稱作非結構化信息管理(UIM)方案。然而，這些方案典型地與諸如文檔分類、聚類以及檢索的問題而非信息的推理和基於機器的信息執行有關。
需要一種方法和系統，其能夠自動地使用非形式化信息創建形式化表示中的元素，使得信息變得適於機器處理。

發明內容
鑑於傳統方法和結構的前述和其它示例性問題、缺點和缺陷，本發明的示例性特徵在於提供一種從非結構化表示生成結構化表示的方法和系統。
在本發明的第一示例性方面，一種用於從非結構化描述生成結構化表示的方法包括由計算機接收非結構化描述，由計算機基於該非形式化描述而生成結構化表示。
在本發明的第二示例性方面，一種用於部署計算機基礎設施以便從非結構化描述生成結構化表示的方法包括將計算機可讀代碼集成到計算系統中。該計算機可讀代碼包括用於接收非結構化描述的指令、以及用於基於該非結構化描述而生成結構化表示的指令。
在本發明的第三示例性方面，一種可由數字數據處理單元執行以便從非結構化描述生成結構化表示的信號承載介質包括接收非結構化描述，並且基於該非結構化描述而生成結構化表示。
在本發明的第四示例性方面，一種用於從非結構化描述生成結構化表示的系統包括用於接收非結構化描述的裝置、以及用於基於該非結構化描述而生成結構化表示的裝置。
為了解決上述問題，本發明的示例性實施例提供了使用領域信息的非結構化描述作為用於結構化該信息的基礎的方案。
本發明的示例性實施例允許用戶通過來自系統的指導或自動幫助，根據領域規則結構化和形式化信息，並且從非結構化輸入產生嚴密的結構化產物。
本發明的示例性實施例使用用於非形式化地描述來自領域的信息的領域特定詞彙表和語法。該詞彙表應當包含足以允許對在詞彙表中產生的語句進行分類的語法結構。
本發明的示例性實施例包括用於非形式化地描述領域的詞彙表和語法的編輯器。
本發明的示例性實施例包括語句分類器，其自動地分類使用詞彙表和語法表達的語句。
本發明的示例性實施例使用形式化元模型，其描述形式化信息應當具有的形式。該模型為可以由詞彙表和語法表示的每個語句類型定義信息的形式化版本的結構。
本發明的示例性實施例包括一個或多個嚮導程序(wizard)，其使領域專家通過一組非形式化信息收集步驟，並且基於所接收的非形式化信息而自動創建元模型元素的實例。
本發明的示例性實施例包括用於每個語句類型的嚮導程序，每當對在編輯器中分類的語句採取操作時，可以調用它。
本發明的示例性實施例使用檢查形式化信息的一致性和完整性的方案。以這種方式，在發現形式化問題時，可以向領域專家提供反饋。
本發明的示例性實施例是有利的，這是因為它使得能夠將非形式化信息轉換成不同於非形式化表示而可由機器處理的形式化表示。使用該技術的形式化大大簡單于手動完成它，並且僅僅需要學習自然語言的結構化詞彙表。自然語言是人類形成的語言，例如英文、法文、中文等。
本發明的示例性實施例是有利的，這是因為它可以提供嚮導程序，其僅僅通過以非形式化表示的方式從用戶接收輸入來為用戶創建形式化表示。
本發明的示例性實施例是有利的，這是因為信息可以在非形式化和形式化表示中同時可用，因而可以由專家和非專家以同樣的方式檢查和分析它。
本發明的示例性實施例是有利的，這是因為從非形式化表示到形式化表示的信息轉換允許通過編程構造來捕獲(capture)信息。這使得能夠完全地執行和推理信息。
這些和很多其它優點可以通過本發明來實現。


根據下面參考附圖對本發明的示例性實施例的詳細描述，將會更好地理解前述和其它示例性目的、方面和優點，其中圖1示出了利用並且併入本發明的示例性硬體/信息處理系統100；
圖2示出了用於存儲根據本發明的方法的程序步驟的信號承載介質200(例如，存儲介質)；圖3示出了根據本發明示例性實施例的形式化環境300；圖4示出了根據本發明的控制例程的示例性實施例的流程圖400，其中該控制例程用於基於由用戶提供的信息的非形式化表示而獲得該信息的形式化表示；圖5示出了用於管理部門502和項目504的簡單系統的示例性數據領域模型500；圖6示出了示例性用例模型600，其示出了圖5的數據領域模型的各個用例606；圖7示出了根據本發明的示例性圖形用戶界面700；圖8示出了根據本發明的示例性實施例的、用於形式化用例的示例性元模型800；圖9示出了根據本發明的示例性圖形用戶界面900；圖10示出了根據本發明的示例性嚮導程序314的示例性圖形用戶界面1000；圖11示出了根據本發明的示例性元模型1100；圖12示出了根據本發明的、用於執行一致性檢查的示例性控制例程1200的流程圖；圖13示出了根據本發明的、用於檢查形式化模型的完整性的控制例程的流程圖1300；圖14示出了根據本發明的、用於形式化「預訂航班」用例語句的嚮導程序314的示例性圖形用戶界面1400；圖15示出了使用圖14的圖形用戶界面1400創建的形式化語句1500；圖16到24示出了用於結構化和形式化信息技術領域內的信息的圖形用戶界面1600的各個操作狀態；圖25示出了用於結構化和形式化音樂領域內的信息的另一個圖形用戶界面2500；
圖26示出了根據本發明示例性實施例的形式化例程的流程圖2600；以及圖27示出了根據本發明示例性實施例的準則(criteria)分析引擎的流程圖2700。
具體實施例方式
現在參考附圖，更具體地說，參考圖1～27，示出了本發明的方法和結構的示例性實施例。
就本描述而言，對『結構化』信息或『結構化』表示的引用意欲表示每一個組成部分都已被給予特定類別並且已被相互排列的信息。
此外，雖然下面描述一般涉及結構化和非結構化信息，但是本領域的普通技術人員應當理解，結構化信息包括形式化信息等，並且非結構化信息包括非形式化信息等。
對『形式化』的引用不僅表示『結構化』信息，而且表示其每個組成部分已被給予特定語義的信息。例如，形式化信息可以包括關於程式語言、建模語言、建築描述語言等中的對象的類型或類的語義。這些語義可以具有特定的組成部分或可能的值和行為。因此，例如，在下面描述中對根據所識別的形式化來生成形式化產物的引用可以包括生成新產物，並且向該新產物給予特定語義。
圖1示出了根據本發明的系統100的典型硬體配置，其中系統100用於從非形式化描述捕獲形式化且嚴密的信息，並且優選地具有至少一個處理器或中央處理單元(CPU)111。
CPU 111通過系統總線112互連到隨機存取存儲器(RAM)114、只讀存儲器(ROM)116、輸入/輸出(I/O)適配器118(用於將諸如盤單元121和磁帶驅動器140的外圍設備連接到總線112)、用戶接口適配器122(用於將鍵盤124、滑鼠126、揚聲器128、麥克風132和/或其它用戶接口設備連接到總線112)、通信適配器134、以及顯示適配器136，其中通信適配器134用於將信息處理系統連接到數據處理網絡、網際網路、內聯網、個人區域網(PAN)等，並且顯示適配器136用於將總線112連接到顯示設備138和/或印表機139(例如，數字印表機等)。
除了上述硬體/軟體環境之外，本發明的不同方面還包括用於執行下述方法的計算機實現方法。作為示例，該方法可以在上述具體環境中實現。
這種方法可以例如通過操作如由數字數據處理設備實施的計算機來實現，以執行機器可讀指令序列。這些指令可以駐留在各種信號承載介質中。
這樣，本發明的這一方面涉及一種編程產品，其包括信號承載介質，該信號承載介質有形地包含可由併入CPU 111和上述硬體的數字數據處理器執行的可機讀指令的程序，以執行本發明的方法。
該信號承載介質可以例如包括包含在CPU 111內的RAM，例如，其由快速存取存儲裝置代表。可選地，這些指令可以包含在可由CPU111直接或間接存取的其它信號承載介質如磁性數據存儲盤200(圖2)中。
無論是包含在盤200中、計算機/CPU 111中或者其它處，這些指令都可以存儲在各種可機讀數據存儲介質上，例如，DASD存儲裝置(例如，傳統的「硬碟驅動器」或RAID陣列)、磁帶、電子只讀存儲器(例如，ROM、EPROM或EEPROM)、光存儲裝置(例如，CD-ROM、WORM、DVD、數字光帶等)、紙式「打孔」卡、或者其它適合的信號承載介質包括諸如數字和模擬通信鏈路以及無線的傳輸介質。在本發明的示例性實施例中，可機讀指令可以包括軟體目標代碼。
圖3示出了根據本發明示例性實施例的形式化環境300，其中用戶302可以基於由用戶302提供的信息的非形式化表示而獲得該信息的形式化表示。
形式化環境300包括編輯器304、語句分類器306、約束檢查器308、約束集310、嚮導程序314的集合312、形式化模型316、以及形式化元模型318。
圖4示出了根據本發明的控制例程的示例性實施例的流程圖400，其中該控制例程用於基於由用戶提供的信息的非形式化表示而獲得該信息的形式化表示。
在本發明的示例性實施例中，用戶302輸入用戶302希望使用本發明300形式化的非形式化描述。用戶302使用相關領域的適當詞彙表。
該控制例程在步驟402開始，並且繼續到步驟404。在步驟404，用戶302激活編輯器，並且控制例程繼續到步驟406。
在步驟406，控制例程確定用戶操作是否指示輸入語句。如果在步驟406，控制例程確定用戶操作指示輸入語句，則控制例程繼續到步驟408。
在步驟408，控制例程解析輸入語句，並且向輸入語句添加小部件(widget)，並且返回到步驟406。
然而，如果在步驟406，控制例程確定用戶操作沒有指示輸入語句，則控制例程繼續到步驟410。
在步驟410，控制例程確定用戶操作是否指示小部件選擇。如果在步驟410，控制例程確定用戶操作指示小部件選擇，則控制例程繼續到步驟412。
在步驟412，控制例程激活嚮導程序，並且返回到步驟406。
然而，如果在步驟410，控制例程確定用戶操作沒有指示小部件選擇，則控制例程繼續到步驟414。
在步驟414，控制例程確定用戶操作是否指示保存請求。如果在步驟414，控制例程確定用戶操作指示保存請求，則控制例程繼續到步驟416。
在步驟416，控制例程保存模型，並且返回到步驟406。
然而，如果在步驟414控制例程確定用戶操作沒有指示保存請求，則控制例程繼續到步驟418。
在步驟418，控制例程確定用戶操作是否指示檢查約束請求。如果在步驟418，控制例程確定用戶操作指示檢查約束請求，則控制例程繼續到步驟420。
在步驟420，控制例程激活約束檢查器，並且返回到步驟406。
然而，如果在步驟418，控制例程確定用戶操作沒有指示檢查約束請求，則控制例程繼續到步驟422，其中控制例程停止。
下面描述如圖3所示的本發明的示例性實施例的操作，其捕獲自動生成測試例來測試軟體系統的軟體系統的形式化模型。
當測試軟體系統時，開發有效且高效的測試集是複雜的問題。如果測試集徹底地覆蓋輸入、操作和操作序列的組合，從而增強它將遇到軟體中的缺陷的可能性，則它是有效的。如果測試集提供這樣的覆蓋而沒有將導致過度增加測試工作的不必要冗餘，則它是高效的。
典型地，當測試者測試軟體系統時，測試者或測試程序對正被測試的系統採取操作，並且從被測試系統接收所返回的結果或響應。將所接收的結果與預期結果進行比較，以確定該系統是否正確工作。然後，測試者採取另一個操作，獲得某個其它響應，並且測試者執行一系列這些操作/響應序列。有時，該序列的次序取決於在該序列中較早接收的響應。序列可被組合的方式的數目非常大。
下面描述涉及用例的概念。用例定義用戶感興趣的一段功能性。換句話說，用例以類似於該系統的用戶視圖的方式呈現被測試系統。例如，在字處理器中，用戶可能想要保存文件。用戶考慮「我將要保存文件」。這樣，「保存文件」成為用例。用例可以包括若干步驟。在本例中，用戶可能點擊「保存為」、鍵入文件名，然後點擊「確定」。系統可能以「該文件名已經存在，想要覆寫它？」響應，並且用戶響應「是」。這樣，對於特定用例可能發生很多操作。這些步驟是用例內的操作。
下面描述還涉及另一個概念，該概念被稱作「參與者」。對於任何給定軟體系統，可以存在很多參與者。參與者的例子可以包括系統管理員、常規用戶和客戶。不同的參與者經常具有僅僅使用特定用例子集的權限。這些子集可以重疊。
本發明的示例性實施例還使用測試例的概念，其是比用例更高級別的構造。測試例是用例序列。每個用例具有可以影響系統狀態的結果，並且還可以向用戶提供某種反饋。作為示例，在「保存文件」用例中，向用戶的反饋可以是「文件被保存」。這樣，在文件被保存的事實中反映了系統狀態。
為了為軟體系統生成有意義的測試例，應當獲得三種信息。第一種信息描述將由軟體系統操縱的數據。第二種數據描述必須由軟體系統滿足的規則(例如，「不變式(invariant)」)。第三種信息提供軟體行為的定義。
這三種信息可以通過對數據使用領域數據模型、對不變式使用數據模型上的約束、以及對行為使用用例(case)來建模。
可以使用本發明的示例性實施例以非形式化方式捕獲並且形式化所有這三種信息。
如上所述，用例是使用描述軟體系統與其用戶(也被稱作參與者)之間的交互的場景(scenario)來定義系統的行為能力的方式。這些用例被描述為語句序列，其中每一個定義使用系統時的步驟。
在本發明的示例性實施例中，存在至少三種語句步驟輸入步驟、輸出步驟、以及計算步驟。輸入步驟是參與者向系統提供某信息的步驟。輸出步驟是系統向參與者返回某信息的步驟。計算步驟涉及系統執行計算的步驟。
為了說明這些能力，考慮下面如圖5所示的、用於管理部門502和項目504的簡單系統的數據領域模型500。部門502和項目504具有名稱(name)506和預算(budget)508。每個部門502可以具有零個或更多個與其相關聯的項目504。項目504與正好一個部門502相關聯。
在該模型500上存在不變式510(也被稱作業務規則)，其規定了部門502中的項目504的所有預算508之和不能超過該部門502的預算508。
除了領域數據模型500之外，該示例還具有圖6所示的用例模型600，其示出了各個用例606。在該模型中存在兩個參與者部門管理者602、以及監管幾個部門502的總監604。
給定用例606，本發明的示例性實施例從領域專家接收詳細描述每個特定用例的交互的非形式化步驟序列。
例如，對於「創建項目」用例606，系統需要部門管理者的授權，向部門管理者詢問名稱、部門和預算，從部門管理者接收名稱、部門和預算，為該部門創建項目。換句話說，「創建項目」用例606的步驟序列如下前提部門管理者已授權1.系統詢問名稱、部門和預算2.部門管理者輸入名稱、部門和預算3.系統創建與指定的部門相關聯的項目。
部門管理者的授權被認為是前提，這是因為在可以執行其餘步驟之前必須滿足該前提。
向部門管理者詢問被分類為輸出步驟。由部門管理者輸入信息被分類為輸入步驟，並且創建項目被分類為計算步驟。
給定上述非形式化軟體系統模型，本發明的示例性實施例根據下面描述創建形式化模型。
本發明的示例性實施例首先使用詞彙表和語法以便捕獲組成用例步驟的語句。
如上所述，存在三類語句輸入步驟、輸出步驟和計算步驟。本發明的示例性實施例基於語句中的動詞而對語句進行分類。在本發明的其它示例性實施例中，除了動詞之外，可以使用其它語法結構。
例如，下面示出了根據本發明示例性實施例的用於語句分類的樣例語法。
輸入::＝參與者名稱[輸入|選擇]信息輸出::＝系統名稱向參與者名稱[顯示|返回]輸出計算::＝系統名稱[創建|計算|更新|刪除]信息在本發明的示例性實施例中，每個語句內的斜體詞可以用自由文本替換，其中自由文本是用戶希望輸入的任何自然語言文本。這樣，有效的計算語句將是ATM系統更新帳戶狀態。
因為該語句指定了對系統內的元素的更新，所以該語句是計算語句。
本發明的示例性實施例包括編輯器和分類器，其中編輯器用於捕獲語句，並且分類器用於將語句分類到由詞彙表定義的語句類型中。分類器以一旦提供模板/嚮導程序機制則分類可以支持語句的形式化的方式對語句進行分類。
在關於上面示例討論的簡單語言的情況下，如圖7所示，編輯器304的圖形用戶界面700可以是具有附加特性的簡單文本編輯器。圖形用戶界面700可以用粗體顯示每個語句704的動詞702，並且將動詞之後的文本712顯示為連結元素。編輯器304基於每個語句的分類而確定如何在圖形用戶界面700中顯示語句內的文本。然後，用戶302可以「點擊」作為連結712而顯示的文本，以便使系統啟動支持對應語句的形式化的適當嚮導程序。
圖形用戶界面700還示出了將不被本描述解決的若干「異常」語句714。然而，這些語法元素全都以相同的方式處理。
由圖形用戶界面700示出的示例性用例對應於從帳戶取款的用例。
圖8示出了根據上述本發明示例性實施例的、用於形式化用例的示例性元模型800。
該元模型示出了「規範化模型」(NormedModel)41(在我們的示例性實施例中，用於形式化模型的名稱)包含四項內容「規範化參與者」(NormedActor)40、「規範化用例」(NormedUseCases)44、「規範化類」(NormedClass)43以及作為「規範化表達式」(NormedExpression)45的業務規則。此外，「規範化類」43包含「規範化屬性」(NormedAttribute)46。「規範化用例」44包含「規範化結果」(NormedResult)48，其由在產生結果時規定的保護(guard)以及「規範化結果更新」(NormedResultUpdate)49語句集組成，其中「規範化結果更新」49語句描述伴隨給定「規範化結果」48的任何計算。「規範化結果」48保護、「規範化結果更新」49以及業務規則全都以作為「規範化表達式」45表示，這是我們的實施例所提供以便捕獲約束和計算語句的共同方式。
根據該示例性實施例，輸入語句引用用戶向系統提供的用例參數。類似地，輸出語句引用系統向參與者輸出的用例參數。計算語句引用當產生特定用例結果時所發生的對(由類和屬性建模的)對象欄位的狀態更新。該結果包括保護和更新語句自身。
就本描述而言，保護是用例中的各個結果上的約束，並且更新語句相同於計算。
如上所述，本發明的示例性實施例包括用戶可以使用編輯器304的圖形用戶界面700激活以形式化語句的嚮導程序314或其它幫助工具。嚮導程序是從用戶接收信息並且為用戶執行自動任務的小程序(程序段)。在這種情況下，嚮導程序314是從用戶接收有關語句的信息以便形式化該語句的小程序。
為了允許通過編輯器304使用嚮導程序314，本發明的示例性實施例依賴於編輯器304的圖形用戶界面700，其在每個語句內顯示「置標」文本。圖形用戶界面700使用允許用戶識別哪些語句需要形式化的標記來顯示語句文本。例如，如上所述，圖形用戶界面700可以通過對文本712加下劃線來標記語句內的文本。以這種方式，當用戶302點擊標記712時，本發明的示例性實施例啟動嚮導程序314，其幫助該語句的形式化。
換句話說，當本發明的示例性實施例確定用戶302選擇了標記712(例如，「點擊連結」)時，則該示例性實施例啟動幫助用戶形式化語句的嚮導程序。
圖10示出了根據本發明的示例性嚮導程序314的圖形用戶界面1000。圖9示出了在動作動詞902之後的文本912上具有置標的圖形用戶界面900。通過該示例性實施例，用戶302點擊在圖9中圈起的置標916導致本發明的示例性實施例啟動如圖10所示的、嚮導程序314的圖形用戶界面1000。
嚮導程序314的圖形用戶界面1000允許用戶302在語句中非形式化表示的信息，本發明的示例性實施例將通過其按照數據模型和輸入參數來形式化語句。用戶302可以在由嚮導程序的圖形用戶界面1000提供的欄位中填寫，並且可以回答由嚮導程序的圖形用戶界面1000提供的任何問題(未示出)。在圖形用戶界面1000中，用戶302可以在「領域對象」欄位1002、「屬性」欄位1004、「參數」欄位1006、以及「常量」欄位1008中輸入信息。然後，當用戶302在其它欄位1002～1008中輸入信息時，圖形用戶界面1000可以在「表達式」欄位1010中提供語句的形式化表示。
在用戶302完成填寫由圖形用戶界面1000提供的欄位1002～1008之後，用戶302可以激活「完成」按鈕1012，以使嚮導程序314保存語句的形式化表示。
由本發明的示例性實施例創建的取款用例的部分形式化(使用擴展置標語句)如下UseCaseNameWithdraw/Name
Preconditionlet User:domainmodel::atmNew::User=archetest::domainmodel::atmNew::User.allInstanees-any(c|true)in User.uebtAttrloggedOn=true/Precondition
Step1InputaccountTypearchetest::domainmodel::atmNew::AccountType/Type
/Input
/Step
Step2InputaccountTypeReal/Type
/Input
/Step2Step3OutputcashTypePhysical Action\Type
/Output
/Step
/Step4Computation
let Account:
archetest::domainmodel::atmNew::Account=archetest::domainmodel::atmNew::Account.allInstances-any(c|true),useCaseInv:
archetest::expressions::UseCaseInvocation=archetest::expressions::UseCaseInvocation.allInstances-any(uc|true),bindings:Sequence(archetest::expressions::Binding)=useCaseInv.bindings,amount:Real=bindings-any(b|b.parameter.name=′amount′).value inAccount.ucbtAttrbalance#Account.ucbtAttrbalance-amount/Computation
/Step/UseCase
以這種方式，本發明的示例性實施例基於使用編輯器304和嚮導程序314由用戶302提供的信息，從元模型318創建一個或多個元類的實例，並且向形式化模型316填充形式化數據。
在本發明的示例性實施例中，在步驟420，約束檢查器308通過檢查形式化模型的一致性和完整性來檢查以確保不違反約束310。在給定領域內，還可以檢查其它屬性(property)(例如，安全性、存活性等)。
約束檢查器308首先基於對於用例的任何給定參數集，應當存在一個並且僅一個結果的事實，檢查一致性。完整性意味著每個輸入組合應當具有為它們定義的結果的相關屬性。
模型的形式化中的約束可以使用對象約束語言(OCL)由本發明的示例性實施例表示。OCL是用於表述模型上的不變式的形式化約束語言。對象約束語言可以用來約束任何模型，包括在形式化中使用的元模型。第一階邏輯(FOL)是提供普遍且存在的量化(quantification)、以及標準命題操作(非、與、或、蘊含以及雙向蘊含)的標準邏輯。一致性通常意味著檢查約束不能相互矛盾，它們也不可通過使得有可能產生兩個結果而引入歧義。完整性通常意味著檢查一組約束形成重言式(tautology)。
圖12示出了根據本發明的、用於執行一致性檢查的示例性控制例程1200的流程圖。約束檢查器308在步驟1202開始，其中創建要被檢查的約束的有序列表，並且約束檢查器308繼續到步驟1204。
在步驟1204，約束檢查器308選擇列表中下一個未被處理的約束，並且將下一個未被處理的約束設為當前語句，並且繼續到步驟1206。
在步驟1206，約束檢查器308確定是否存在當前語句下的約束。如果在步驟1206，控制例程確定存在當前約束下的約束，則約束檢查器308繼續到步驟1210。
在步驟1210，約束檢查器308使用邏輯推理來確定是否能夠同時滿足當前約束和當前語句下的任何約束，並且繼續到步驟1212。
在步驟1212，約束檢查器308根據是否能夠同時滿足當前約束和當前語句下的任何約束而分支。如果在步驟1212約束檢查器308確定能夠同時滿足當前約束和當前約束下的任何約束，則控制例程繼續到步驟1214。
在步驟1214，約束檢查器308向用戶報告不一致，並且繼續到步驟1216，其中約束檢查器308完成。
然而，如果在步驟1212，約束檢查器308確定不能同時滿足當前約束和當前語句下的任何約束，則約束檢查器308返回到步驟1204。
然而，如果在步驟1206，約束檢查器308確定不存在當前約束下的元素，則約束檢查器308繼續到步驟1208。在步驟1208，約束檢查器308報告該模型一致，並且繼續到步驟1216，其中約束檢查器308停止。
以這種方式，約束檢查器308檢查形式化模型的一致性。
圖13示出了用於檢查形式化模型316的完整性的控制例程的流程圖1300。約束檢查器308在步驟1302開始，並且創建領域模型的所有用例的有序列表，並且繼續到步驟1304。
在步驟1304，約束檢查器308將當前用例設為列表中的下一個用例，並且繼續到步驟1308。在步驟1308，約束檢查器308創建用例中的所有約束的析取(disjunction)D，並且繼續到步驟1310。
在步驟1310，約束檢查器308確定析取D是否是重言式。如果在步驟1310，約束檢查器308確定析取D不是重言式，則約束檢查器308繼續到步驟1312，並且報告用例的不完整。
然而，如果在步驟1310，約束檢查器308確定析取D是重言式，則約束檢查器308繼續到步驟1306。
在步驟1306，約束檢查器308確定是否存在更多要處理的用例。如果在步驟1306，約束檢查器308確定存在更多要處理的用例，則約束檢查器308返回到步驟1304。
然而，如果約束檢查器308確定不存在更多要處理的用例，則約束檢查器308繼續到步驟1314，其中約束檢查器308的操作停止。
以這種方式，約束檢查器308的示例性實施例可以檢查形式化模型的完整性。
參考圖14和15示出本發明的示例性實施例在其中是有用的應用的另一個示例。
在該第二示例中，本發明可以用來生成複雜的旅行計劃。在本例中，可以定義與上述用例的語法類似的語法，這允許用戶談論旅行日期、城市、航線、旅館、計程車、旅館、吸引力(attraction)等。通過本發明，用戶因而將能夠以非形式化格式將期望旅程描述為步驟序列。
例如，用戶可能為從紐約到巴黎的旅程提供下面旅程序列。
1.在2005年12月22日從紐約飛往巴黎。
2.逗留3天。
3.在2005年12月23日在L』Entrecote用餐4.在2005年12月26日從巴黎乘火車到卡爾卡松尼5.在卡爾卡松尼逗留7天。
6.在2006年1月2日返回巴黎。
7.逗留一晚。
8.在2006年1月3日返回紐約。
給定該描述，本發明的示例性實施例將形式化可以由諸如計算機等的機器自動處理的旅程描述。為了簡單起見，下面描述將僅僅考慮旅行、旅館、預訂以及進餐選擇，不過，本領域的普通技術人員應當理解，本發明的示例性實施例可以有利地有用於形式化旅程的所有方面。
給定上面旅程描述中的語句類型，將需要把將用於形式化語句的元模型318提供給形式化環境300。圖11示出了併入必要特徵的示例性元模型1100。
給定語言和元模型1100，現在提供嚮導程序314，其將用來進一步精煉(refine)由非形式化描述捕獲的信息。
圖14示出了用於形式化「預訂航班」用例語句的嚮導程序314的示例性圖形用戶界面1400。該圖形用戶界面1400對應於上面提供的非形式化描述中的第一語句。以類似於前述的方式，用戶將信息輸入到圖形用戶界面1400中，並且嚮導程序314獲得輸入信息，並且創建形式化語句1500，如圖15所示。
本發明的第三示例性實施例用作讓用戶結構化信息技術(「IT」)系統架構的領域內的信息的工具。就本描述而言，信息技術可以是指如在Astandard for architecture description，R.Youngs，D.Redmond-Pyle，P.Spaas、以及E.Kahan，IBM Systems Journal 38(1)1999，第32～50頁中定義的IT系統架構。
現在參考附圖，並且更具體地參考圖16，圖16示出了根據本發明的示例性圖形用戶界面1600。
在示例性實施例中，圖形用戶界面1600可能被實現為諸如Eclipse的平臺的擴展，其在EclipseA Platform Becomes an Open-SourceWoodstock，A.Wolfe，ACM Queue 1(8)，2003年11月，第14～16頁中有描述。
圖形用戶界面1600包括描述區域1601，用戶可以將包括非結構化信息的非形式化描述輸入到其中，並且在其中用戶可以識別非形式化描述的部分；形式化區域1602，在其中可以列出候選形式化，並且在其中用戶可以識別形式化；產物(Artifact)區域1603，在其中可以列出基於所識別的非形式化描述的部分、根據所識別的形式化所生成的形式化產物；以及建議區域1604，在其中可以顯現由該工具輸出的建議。
在該示例性實施例中，候選形式化涉及例如可以在Youngs等人的參考文獻中定義的、來自IT系統架構領域的產物，包括參與者、用例、場景(Scenario)、協作、組件、接口等。
在該示例性實施例中，可以預定義候選形式化列表。圖16示出了緊接在啟動了根據本發明的形式化例程之後並且用戶執行了任何操作之前的圖形用戶界面1600。
圖26示出了根據本發明的、用於將非結構化信息轉換成結構化信息的示例性控制例程2600的流程圖。
現在參考圖16～26，將描述本發明的示例性實施例的操作。
形式化例程在步驟2601開始，並且繼續到步驟2602。在步驟2602，形式化例程等待用戶執行操作。一旦接收到用戶操作，則形式化例程繼續到步驟2603。
在步驟2603，形式化例程確定用戶操作是否是描述編輯操作。例如，形式化例程可以確定用戶在描述區域1601中執行編輯操作。如果在步驟2603，形式化例程確定用戶操作是描述編輯操作，則該工具繼續到步驟2604。在步驟2604，形式化例程編輯描述，並且返回到步驟2602。
在本發明的示例性實施例中，編輯操作可以簡單地是如在許多通常可用的編輯應用中可能發現的傳統文本或圖形編輯。
例如，在本發明的示例性實施例中，標準編輯器如OpenOffice字處理器或者編輯模式中的Firefox HTML瀏覽器可以與本發明一起使用。
此外，本發明的示例性實施例可以使用具有包裝器(wrapper)的標準編輯器，其為形式化例程提供對編輯器內容的訪問，以及提供通過形式化例程對編輯器的控制。可以支持的示例性編輯操作包括將內容粘貼到區域中、選擇內容的多個部分、刪除或插入內容、改變內容的格式等。
再次參考圖26，在步驟2605，形式化例程確定用戶操作是否是部分識別操作。如果在步驟2605形式化例程確定用戶操作是部分識別操作，則形式化例程繼續到步驟2606，其中形式化例程突出(highlight)通過部分識別操作識別的部分，並且返回到步驟2602。
例如，圖17示出了在某內容已被放置到描述區域1700中之後圖形用戶界面1600的顯現。在本例中，內容涉及唱片公司的音樂網站的需求，並且用戶在描述區域1601中執行部分識別操作。
如上所述，本發明能夠在步驟2605識別出部分識別操作，並且作為響應，形式化例程繼續到步驟2606，其中形式化例程突出通過部分識別操作識別的描述的部分。
在本發明的示例性實施例中，部分識別操作可以簡單地是標準選擇操作，例如可能用來在OpenOffice字處理器中選擇短語的操作(例如，雙擊詞，在短語上拖動光標等)。
在本發明的示例性實施例中，突出所識別的部分可以簡單地是標準選擇指示，例如可能用來在OpenOffice字處理器中指示所選短語的操作(例如，改變短語背景和前景顏色)。
然而，如果在步驟2605，形式化例程確定用戶操作不是部分識別操作，則形式化例程繼續到步驟2607。
在步驟2607，形式化例程確定用戶操作是否是形式化識別操作。作為示例，圖18示出了在用戶識別了詞『artists(藝術家)』1800之後的圖形用戶界面1600，並且圖19示出了用戶識別了『參與者』形式化1900之後的圖形用戶界面1600。
如果在步驟2607，形式化例程確定用戶操作是形式化識別操作，則形式化例程繼續到步驟2608。
在步驟2608，形式化例程基於所識別的非形式化描述的部分1800、根據所識別的形式化1900，生成形式化產物2608，並且繼續到步驟2609。在步驟2609，形式化例程根據所識別的描述的部分1800，為所生成的形式化產物設置標籤(label)，並且繼續到步驟2610，其中形式化例程應用準則分析引擎，下面參考圖27描述其示例。
圖20示出了生成了以『artists』2000標註的形式化參與者產物的圖形用戶界面1600。
以這種方式，通過本發明的示例性實施例，用戶可以指示IT系統必須與被稱作「artists」的外部用戶交互，並且可以將該指示形式化為系統架構的結構化表示中的產物。
圖21示出在識別了短語『post news(張貼新聞)』2100之後並且在用戶識別用例形式化2101時的圖形用戶界面1600。
圖22示出了根據用例形式化2101生成了post news產物2200之後的圖形用戶界面1600。
以這種方式，用戶可以將非形式化描述的一部分識別為對應於用例形式化，並且基於該識別而獲得系統的結構化表示中的形式化產物。
圖27示出了根據本發明示例性實施例的準則分析引擎的流程圖2700。準則分析引擎可以在圖26的步驟2610或2613由形式化例程初始化。
準則分析引擎在步驟2701開始，並且繼續到步驟2702，其中準則分析引擎刪除可能已經在圖形用戶界面1600的建議區域1604中提供的任何先前建議。
然後，準則分析引擎繼續到步驟2703，其中準則分析引擎定位到與形式化產物有關的一組準則中的第一準則，並且繼續到步驟2704。
在示例性實施例中，可以預定義這組準則。就本描述而言，與形式化產物有關的準則可以包括與形式化產物的屬性相關的條件。例如，準則可能是「其標籤不包括被稱作『標識符』的第一字符串、隨後的下劃線字符、隨後的第二字符串的用例產物」。
在示例性實施例中，可能使用如在Perl程式語言中定義的模式或正規表達式(regular expression)來表達，其中Perl程式語言的描述可以在Programming Perl，L.Wall，T.Christiansen、以及J.Orwant，「(第三版)」，O′Reilly，2000年7月中找到。
作為準則的另一個例子，準則可能是「沒有對應的場景產物的用例產物，其中用例產物標籤標識符是場景產物標籤識別符的前綴」。本領域的一般技術人員應當理解，根據本發明，很多其它類型的準則是可能的而不存在限制。
再次參考圖27，在步驟2704，準則分析引擎確定是否處理了所有準則。如果在步驟2704，準則分析引擎確定處理了所有準則，則控制例程繼續到步驟2711，其中準則分析引擎結束。
然而，如果在步驟2704，準則分析引擎確定尚未處理所有準則，則準則分析引擎繼續到步驟2705，其中準則分析引擎定位到第一產物，並且繼續到步驟2706。
在步驟2706，準則分析引擎確定是否處理了所有產物。如果在步驟2706，準則分析引擎確定處理了所有產物，則準則分析引擎繼續到步驟2709。
在步驟2709，準則分析引擎定位到下一個準則，並且返回到步驟2704。
然而，如果在步驟2706，準則分析引擎確定了尚未處理所有產物，則準則分析引擎繼續到步驟2707，其中準則分析引擎確定準則分析引擎所定位的產物是否滿足準則分析引擎所定位的準則。
如果在步驟2707，準則分析引擎確定該產物確實滿足該準則，則準則分析引擎繼續到步驟2708，其中準則分析引擎在識別產物的建議區域1604中產生輸出。然後，準則分析引擎繼續到步驟2709。
在本實施例中，產生產物的標籤作為輸出。另外，可以在建議區域1604中產生與產物有關的建議作為輸出。
如果在步驟2707，準則分析引擎確定了該產物不滿足該準則，則準則分析引擎繼續到步驟2709。
再次參考圖22，圖22示出了在輸出了被標註為「post news」的形式化用例產物2200和建議2201之後的圖形用戶界面1600的外觀。
建議的示例可以包括與用戶希望作為結構化和形式化非形式化描述的處理的一部分而執行的另外操作有關的指導。建議可以基於已經生成的產物集的當前主體。在該示例性實施例中，建議不僅僅基於處理的某靜態定義，並且不是必須被用戶立即注意到的東西，或者是根本無需被用戶注意到的東西。相反，對於該示例性實施例，建議是每當出現機會時用戶可能希望注意到的東西。
在本發明的示例性實施例中，建議不是不一致或其它錯誤的指示。相反，建議可以指示可改進(形成中的)結構化表示的當前狀態的方式。
圖22所示的示例性建議2201是這樣的建議，即改變標籤以使其遵循標籤包括被稱作『標識符』的第一字符串、隨後的下劃線字符、隨後的第二字符串的約定。
在該示例性實施例中，每當存在對已經生成的產物集的狀態的改變(例如，如參考步驟2609和2612所述)時，可以重新計算建議集。
在該示例性實施例中，可以每次重新計算整個建議集。然而，本領域的普通技術人員應當理解，根據本發明，通過僅僅考慮可能受到最近狀態改變的影響的那些產物、準則和建議，可以增量更新建議集。
再次參考圖27，在步驟2708，準則分析引擎定位到下一個產物，並且返回到步驟2706。類似地，在步驟2709，準則分析引擎定位到下一個準則，並且返回到步驟2704。
圖23示出了在描述區域2301中識別了非形式化描述的多個部分、在每例中識別了來自形式化區域2302的形式化、在每例中相應地生成了形式化產物、在每例中在產物區域2303中顯現了形式化產物，並且在建議區域2304中顯現了對應的建議之後的圖形用戶界面1600。
再次參考圖26，在步驟2611，控制例程確定用戶操作是否是產物重命名操作。如果在步驟2611，控制例程確定用戶操作是產物重命名操作，則控制例程繼續到步驟2612。
在步驟2612，控制例程根據用戶的指令執行產物的重命名，並且繼續到步驟2613，其中應用準則分析引擎。然後，控制例程返回到步驟2602。
在該示例性實施例中，用戶的重命名操作可以包括在產物區域1603中雙擊形式化產物，並且為它輸入新標籤。
圖24示出了用戶通過執行重命名操作來響應建議2305之後的圖形用戶界面1600，其中該重命名操作將用例產物2306的標籤從『create aportal(創建門戶)』改變為『UC01_reate portal』，從而導致用例產2400以『UC01_Create portal』標註。
另外，圖24示出了建議2305不再在建議區域中，但是現在已經輸出了與該用例產物有關的不同建議2401。
再次參考圖26，如果在步驟2611，形式化例程確定用戶操作不是產物重命名操作，則形式化例程繼續到步驟2614。
在步驟2614，形式化例程確定用戶操作是否是保存操作。如果在步驟2614，形式化例程確定用戶操作是保存操作，則形式化例程繼續到步驟2615。
在步驟2615，形式化例程保存形式化產物，並且返回到步驟2602。
然而，如果在步驟2614，形式化例程確定用戶操作不是保存操作，則形式化例程繼續到步驟2616。在步驟2616，形式化例程確定用戶操作是否是退出操作。如果在步驟2616，形式化例程確定用戶操作不是退出操作，則形式化例程返回到步驟2602。否則，形式化例程繼續到步驟2617，其中形式化例程結束。
在示例性實施例中，退出操作可以簡單地包括在用戶界面的任何區域中輸入字符『Q』。
示例性實施例可以另外允許在辦公應用中通常找到的許多操作，例如OpenOffice程序集中的操作。它們可能例如對應於如同在例如步驟2615一樣保存工具的當前狀態。可以將工具的當前狀態保存到例如持久性存儲裝置例如盤上的文件等。另外，操作還可以允許從持久性存儲裝置裝載系統的狀態。
本發明的第四示例性實施例用作讓用戶結構化配樂領域內的信息的工具。
參考圖25，與圖16～24的圖形用戶界面1600類似的示例性圖形用戶界面2500包括描述區域2501，用戶可以將包括非結構化信息的非形式化描述輸入到其中，並且在其中用戶可以識別非形式化描述的部分；形式化區域2502，在其中該工具可以列出候選形式化，並且在其中用戶可以識別形式化；產物區域2503，在其中該工具可以列出基於所標識的非形式化描述的部分、根據所識別的形式化而可以生成的形式化產物；以及建議區域2504，在其中可以顯現建議。
在該示例性實施例中，候選形式化涉及來自音樂領域的產物，包括樂句(Phrase)、樂段(Segment)、樂旨(Motif)、韻律(Verse)、合唱(Chorus)、過渡樂節(Bridge)等。這些產物是熟練於配樂領域的普通人員所熟悉的概念。
圖25示出了音樂已被輸入到描述區域2501中之後的圖形用戶界面2500。在示例性實施例中，可以使用來自諸如在The MIDI Manual，David Miles Huber，Focal Press，1991年1月中描述的應用的複製和粘貼功能，將樂譜輸入在描述區域2501中。
另外，圖25示出了在識別了描述的部分2505之後並且在用戶識別『Phrase』形式化2506時的圖形用戶界面2500。
最後，圖25示出了在描述區域2501中識別了非形式化描述的多個部分(例如，2505)、為每個所識別的部分識別了來自形式化區域2502的形式化、並且針對每個所識別的部分相應地生成了形式化產物，並且針對每個所識別的部分在產物區域2503中顯現了形式化產物之後的圖形用戶界面2500。
形式化產物集2503包括被標註為『Golum theme』、『Hobbit villagetheme』和『Frodo theme』的形式化產物。
在所有其它方面，第四示例性實施例的工具的操作類似於第三示例性實施例的工具的操作。
雖然本發明在上面被描述為有利地用於測試例生成、旅遊計劃、IT系統架構以及配樂，但是本領域的普通技術人員應當理解，本發明也可以有利地應用於可以結構化和形式化非結構化的非形式化信息的任何應用。例如，本發明的示例性實施例不加限制地有用於形式化引起產品問題的事件序列、形式化在商業中應當遵循的過程、描述和形式化醫療過程、形式化科學實驗等。
雖然上面描述提供了計算機編程和音樂領域內的信息，但是本領域的普通技術人員應當理解，本發明適用於可以提供分類詞彙表和形式化元模型的任何領域。
雖然本發明是按照若干示例性實施例來描述的，但是本領域的技術人員應當認識到可以加以修改地實施本發明。
此外，應當注意，本申請人的意圖是囊括所有權利要求元素的等價物，即使以後在審查期間有修改的話，也是如此。
權利要求
1.一種用於從非結構化描述生成結構化表示的方法，包括由計算機接收非結構化描述；以及由所述計算機基於所述非結構化描述而生成結構化表示。
2.如權利要求1所述的方法，其中所述非結構化描述包括文本。
3.如權利要求1所述的方法，其中所述非結構化描述包括圖形。
4.如權利要求1所述的方法，還包括接收所述非結構化描述的部分的識別。
5.如權利要求4所述的方法，還包括為所述非結構化描述的所述識別部分接收候選分類的識別。
6.如權利要求5所述的方法，其中所述生成包括基於所述識別部分的所述識別候選類別，生成結構化產物。
7.如權利要求1所述的方法，還包括接收用戶輸入；以及基於所述用戶輸入，構造結構化產物。
8.如權利要求1所述的方法，其中所述結構化表示包括軟體表示。
9.如權利要求1所述的方法，其中所述生成包括參考元模型。
10.如權利要求1所述的方法，其中所述結構化表示包括軟體測試序列。
11.如權利要求1所述的方法，其中所述生成包括識別所述非結構化描述的特徵。
12.如權利要求1所述的方法，其中所述生成還包括對所述特徵進行分類；以及執行請求關於所述分類特徵的信息的嚮導程序。
13.如權利要求12所述的方法，其中所述嚮導程序基於元模型而將所述分類特徵轉換成實例元素。
14.如權利要求1所述的方法，還包括接收與結構化產物有關的至少一個準則；以及提供滿足所述至少一個準則的至少一個結構化產物。
15.如權利要求14所述的方法，其中所述至少一個準則包括描述良好形式化的、基於規則的約束。
16.如權利要求14所述的方法，其中所述至少一個準則包括至少一個語義規則。
17.如權利要求14所述的方法，還包括基於所述結構化產物準則，向用戶提供至少一個建議。
18.一種用於部署計算機基礎設施以便從非結構化描述生成結構化表示的方法，包括將計算機可讀代碼集成到計算系統中，該計算機可讀代碼包括用於接收非結構化描述的指令；以及用於基於所述非結構化描述而生成結構化表示的指令。
19.一種可由數字數據處理單元執行以便從非結構化描述生成結構化表示的信號承載介質，包括接收非結構化描述；以及基於所述非結構化描述而生成結構化表示。
20.一種用於從非結構化描述生成結構化表示的系統，包括用於接收非結構化描述的裝置；以及用於基於所述非結構化描述而生成結構化表示的裝置。
全文摘要
本發明公開一種用於從非結構化描述生成結構化表示的方法和系統，所述方法包括由計算機接收非結構化描述；以及由計算機基於該非結構化描述而生成結構化表示。
文檔編號G06F17/30GK1869989SQ20061008503
公開日2006年11月29日 申請日期2006年5月22日 優先權日2005年5月23日
發明者史蒂夫·埃伯拉姆斯, 巴德·布盧姆, 馬修·卡普蘭, 保羅·T.·凱瑟, 道格拉斯·N.·克梅爾曼, 埃裡克·M.·內爾森, 溫迪·D.·紐伯格, 託瓦·羅斯, 伊恩·西蒙斯, 史蒂文·S.H.·唐, 約翰·M.·維斯迪斯, 克萊·E.·威廉斯 申請人:國際商業機器公司