程序員常利用現有的應用程序介面建立新程序，但遇到的困難是花很多時間去找尋并學習適當的應用程序介面 [8]。在這篇論文中，我們提出新方向幫助對某應用程序介面比較陌生的程序員：以短語搜尋應用程序介面連通子圖。我們以一大圖表達應用程序介面的調用，當用家提交一組文字短語后，便能從這大圖中找出一個符合需要的最理想連通子圖。 / 這新方向的挑戰是簡單的子圖搜尋需要很大的搜尋空間。我們提出兩組機制改良了一套現有的貪婪子圖搜尋算法，以此找出一個其節點與搜尋短語的文字相近的連通子圖。另外，這套現有的貪婪子圖搜尋算法需要很短的圖節點之間的最短路徑計算時間，我們提出了一套空間效率高的索引，能較快的找出節點間的精確最短路徑。從實驗中，我們通過兩組現實生活中的搜尋數據比較了此新方法與一最新式的程序碼建議方法Portfolio [19]，發現兩組數據的平均F₁-Measure能分別有效地提高了64%與36%。 / Reusing APIs of existing libraries is a common practice during software development, but searching suitable APIs and their usages can be time-consuming [8]. There have been studies to help users nd usages of APIs given names of functions. In this paper, we study a new and more practical approach to help users nd usages of APIs given only simple text phrases expressed in natural language, when users have limited knowledge about an API library. We model API invocations as an API graph and aim to nd an optimum connected subgraph that meets users’ search needs. / The problem is challenging since the search space in an API graph is very huge. We start with a greedy subgraph search algorithm which returns a connected subgraph containing nodes with high textual similarity to the query phrases. Two renement techniques are proposed to improve the quality of the returned subgraph. Furthermore, as the greedy subgraph search algorithm relies on online query of shortest path between two graph nodes, we propose a space-effcient compressed shortest path indexing scheme that can eciently recover the exact shortest path. We conduct extensive experiments to show that the proposed subgraph search approach for API recommendation is very eective in that it boosts the average F₁-measure of the state-of-the-art approach, Portfolio [19], on two groups of real-life queries by 64% and 36% respectively. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Chan, Wing Kwan. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 59-62). / Abstracts also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation & Challenges --- p.2 / Chapter 1.2 --- Contributions --- p.4 / Chapter 1.3 --- Organization of Thesis --- p.5 / Chapter 2 --- Related Works --- p.7 / Chapter 2.1 --- Keyword Search in Graphs --- p.7 / Chapter 2.2 --- Team Formation in Expert Network --- p.8 / Chapter 2.3 --- API/Code Recommendation --- p.10 / Chapter 3 --- Problem Statement & Proposed Approach --- p.12 / Chapter 3.1 --- Problem Statement --- p.12 / Chapter 3.2 --- API Subgraph Search --- p.15 / Chapter 3.2.1 --- A Greedy Subgraph Search Algorithm --- p.16 / Chapter 3.2.2 --- Selecting Node with High Textual Similarity --- p.19 / Chapter 3.2.3 --- Handling Multiple Shortest Paths Problem --- p.21 / Chapter 3.2.4 --- Time Complexity --- p.24 / Chapter 3.2.5 --- Approximation Ratio --- p.25 / Chapter 3.3 --- Class-Only Path Indexing --- p.25 / Chapter 3.3.1 --- Three Indexing Structures --- p.27 / Chapter 3.3.2 --- Exact Path Recovery --- p.28 / Chapter 3.3.3 --- Space Complexity --- p.30 / Chapter 3.4 --- Alternative Approaches --- p.31 / Chapter 3.4.1 --- Enhanced Steiner Tree --- p.31 / Chapter 3.4.2 --- Finding R-clique --- p.32 / Chapter 4 --- Experiments --- p.35 / Chapter 4.1 --- Effectiveness - Among Subgraph Searching Algorithms --- p.35 / Chapter 4.1.1 --- Dataset --- p.35 / Chapter 4.1.2 --- Results --- p.36 / Chapter 4.2 --- Effectiveness - Between Two API Recommendations --- p.38 / Chapter 4.2.1 --- Query Formulation --- p.39 / Chapter 4.2.2 --- Results --- p.41 / Chapter 4.3 --- Effciency - Runtime --- p.44 / Chapter 4.4 --- Indexing Comparison Class Graph Vs. Full Graph --- p.46 / Chapter 4.4.1 --- Runtime & Memory --- p.46 / Chapter 4.4.2 --- Gain Score --- p.48 / Chapter 4.5 --- A Comparison with Finding R-Clique --- p.49 / Chapter 4.6 --- Threats to Validity --- p.50 / Chapter 5 --- Conclusion & Future Works --- p.55 / Chapter 5.1 --- Conclusion --- p.55 / Chapter 5.2 --- Future Works --- p.56 / Bibliography --- p.59
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_328635 |
| Date | January 2012 |
| Contributors | Chan, Wing Kwan., Chinese University of Hong Kong Graduate School. Division of Systems Engineering and Engineering Management. |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography |
| Format | electronic resource, electronic resource, remote, 1 online resource (vii, 62 leaves) : ill. (some col.) |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0018 seconds