[發明專利]用于串變換的歸納合成的排序

在審

• 申請號: 201380054348.2
• 申請日: 2013-10-17
• 公開（公告）號: CN104737155A
• 公開（公告）日: 2015-06-24
• 發明（設計）人: S·古爾瓦尼;R·辛格
• 申請（專利權）人: 微軟公司
• 主分類號: G06F17/22
• 分類號: G06F17/22
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 管琦琦

背景

世界范圍內的數百萬人使用電子表格等來存儲和操縱數據。這些數據操縱場景通常包括將大量的輸入信息從一種格式轉換為另一種格式以產生所需輸出。通常，手動地或使用小的、通常是一次性的計算機程序來實現這些任務，這些計算機程序由終端用戶創建或由程序員為終端用戶來創建。

另一種辦法涉及采用計算機來合成程序以實現所需數據變換的嘗試。存在合成程序的兩種主要的辦法：演繹和歸納。在演繹程序合成中，完整的高級規范被轉換成對應的低級程序，其中使用一些公理來驗證轉換中的每個步驟。這一辦法需要用戶提供完整的規范，這在一些情況下可能潛在地比編寫寫程序本身更加困難。這導致歸納合成辦法近來變得更加流行。在歸納程序合成辦法中，從不完整的規范(諸如包括輸入-輸出示例集合的規范)來合成程序。它近來被用于合成從低級指針操縱代碼到電子表格宏的各種領域內的程序。

由于歸納程序合成辦法中的規范是不完整的且經常是不清楚的，存在具有符合給定規范的底層領域專用語言的許多不同程序。為了消除不清楚以及收斂成想要的程序，用戶需要通過提供附加的輸入-輸出示例來加強規范。示例的數目與領域專用語言的表達性直接成比例，即該語言表達的越多，收斂成想要的程序所需的輸入-輸出示例就越多。

領域專用語言需要是可表達的以表達用戶想要的最多任務，但同時不能預期用戶提供數量繁重的輸入-輸出示例以學習想要的程序。

發明內容

本文中所描述的排序技術實施例一般涉及通過使用用戶僅提供少量輸入-輸出示例的歸納程序合成過程來生成的排序候選變換程序。在一個實施例中，計算機被用于排序候選變換程序以建立對一個或多個變換程序的經排序組，每個變換程序從用戶輸入的每個輸入串產生具有用戶想要形式的輸出串，符合用戶提供的一個或多個輸入-輸出示例中的每一個。

更具體而言，輸入候選變換程序的集合。要注意，每個變換程序由具有領域專用語言的程序表達式組成，該程序表達式進一步由子表達式組成。從用于在候選變換程序中發現的子表達式的離線訓練數據建立排序機制。這些排序機制中的每一個產生似然度分數，該似然度分數指示子表達式是能夠從用戶輸入的每個輸入串產生具有用戶想要形式的輸出串的程序的一部分的似然度，其符合用戶提供的輸入-輸出示例中的每一個。對于已經為其建立了排序機制的每個候選變換程序的每個子表達式，使用為該子表達式建立的排序機制來建立似然度分數。按從較小子表達式到較大子表達式的次序計算似然度分數。隨后從為該候選變換程序建立的子表達式似然度分數計算針對每個候選變換程序的總排序分數。

在一個實施例中，使用與候選變換程序中的每一個相關聯的總排序來選擇規定數目的排序在前的候選變換程序。這些排序在前的程序隨后被指定為上述的對一個或多個變換程序的經排序組。要注意在一個實現中，該規定數目為1，且因此僅選擇和指定排序最高的候選變換程序。

應該注意，提供本發明內容是為了以簡化的形式介紹將在以下詳細描述中進一步描述的一些概念。本發明內容不旨在標識出所要求保護的主題的關鍵特征或必要特征，也不旨在用于幫助確定所要求保護的主題的范圍。

附圖簡述

參考以下描述、所附權利要求書以及附圖，將更好地理解本發明的具體特征、方面和優點，附圖中：

圖1是大體概述用于排序候選變換程序的過程的一個實施例的流程圖。

圖2是大體概述圖1的過程中涉及為原子表達式建立排序機制部分的實現的流程圖。

圖3是大體概述圖2的過程中涉及從任務的訓練集合產生訓練數據部分的實現的流程圖。

圖4是大體概述圖3的過程中涉及從正訓練子表達式和負訓練子表達式集合中的每個子串表達式產生訓練數據部分的實現的流程圖。

圖5是大體概述圖1的過程中涉及使用排序機制為候選變換程序的每個子表達式建立似然度分數部分的實現的流程圖，其中已經為每個子表達式建立了該排序機制。

圖6是大體概述用于使用最高排序的候選變換程序執行串變換的過程的一個實施例的流程圖。

圖7是描繪具有輸入欄和輸出欄的電子表格的表，其中所述輸入欄包含標識一個人姓氏的輸入串，所述輸出欄具有含對應輸入串名連同置于該對應輸入串名之前的串“先生(Mr.)”的一個示例輸出串。

圖8是描繪具有輸入欄和輸出欄的電子表格的表，其中所述輸入欄包含包括城市名稱的地址，所述輸出欄具有含對應輸入串中與城市名稱相對應的一部分的一個示例輸出串。

圖9是描繪構成用于實現本文中所述的各排序技術實施例的示例系統的通用計算設備的圖。

詳細描述