[發明專利]有序列表匹配方法和設備、文檔字符匹配方法和設備

有效

• 申請號: 201310018781.2
• 申請日: 2013-01-18
• 公開（公告）號: CN103942200B
• 公開（公告）日: 2017-08-18
• 發明（設計）人: 黃耀海;譚誠;陳明
• 申請（專利權）人: 佳能株式會社
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中國國際貿易促進委員會專利商標事務所11038
• 代理人: 康建忠

技術領域

本發明涉及用于有序列表匹配的方法和設備。此外，本發明涉及用于文檔字符匹配的方法和設備。

背景技術

在文檔處理的領域中，文檔中的字符往往被轉換成有序列表以便被處理。因此，常常對有序列表進行處理以在有序列表之間實現匹配。

當前，在索引系統（諸如全文搜索（FTS）系統）中常常使用兩個有序列表的匹配。在索引系統中，如本領域公知的，使用許多倒排表（inverted table）來幫助提高搜索/操作速度。每個倒排表均是有序列表，并且不同元素類型（諸如字符、單詞、詞干（trunk）等）涉及不同的倒排表。因此，利用倒排表，文檔中包含的內容將被轉換成有序列表以用于進一步的處理，諸如匹配、搜索等。

下文，將參照圖1A至1D描述現有技術中的常用的用于文檔字符索引和匹配的處理。

如圖1A所示，許多文檔中的漢語詞語“日本”將被處理。在識別期間，該詞語中的每個字符、即“日”和“本”將分別被索引。例如，文檔中的字符“日”將用分別指示包含該字符的文檔以及該字符在各文檔中的位置的文檔索引和字符位置索引來索引。通過這樣的處理，字符“日”和“本”中的每一個將具有兩個有序列表，一個有序列表對應于文檔索引，另一個有序列表對應于字符位置索引。

此后，將處理所獲得的字符“日”和“本”的有序列表。更具體而言，將所獲得的字符“日”和“本”的有序列表進行匹配，其中一方面，如圖1B所示，字符“日”和“本”中的每一個的文檔索引列表將被進行匹配，其中為了清楚起見，字符“日”和“本”的文檔索引列表已被處理以便不包括重復元素，但是文檔索引列表可具有重復元素，并且另一方面，如圖1C所示，字符“日”和“本”中的每一個的字符位置索引列表將被進行匹配。最終，如圖1D所示，各文檔中的詞語“日本”將被找到。

存在多種類型的對兩個有序列表進行匹配的方法，并且這些類型的匹配方法通常使用二值搜索方法（binary search method）以及其他類型的搜索方法來實現匹配，其中二值搜索方法是用于有序列表的快速方法。現有技術中的用于對兩個有序列表進行匹配的常用方法可在下文被稱為二值搜索方法，在該方法中，輸入兩個有序列表，其中這兩個有序列表之一用作源列表并且另一個有序列表用作目標列表，并且源列表通常具有比目標列表中的元素更少的元素，該方法對于源列表中的元素進行循環（loop）并且搜索目標列表中的與該源列表中的各元素對應的匹配元素。

將參照圖2以及圖3A至3F描述二值搜索方法。圖2示出現有技術中的二值搜索方法的流程圖，并且圖3A至3F示出應用該二值搜索方法的實例。

在圖2中的步驟100中，輸入兩個有序列表分別作為源列表和目標列表。通常，尺寸較小的列表被設定為源列表，并且尺寸較大的列表被設定為目標列表。這意味著該方法從源列表中選擇元素，并且在目標列表中搜索該元素。

在圖2的步驟200中，確定源列表中的所有元素是否已被搜索。更具體而言，該方法循環源列表，并且判斷所有元素是否已被選擇。如果存在一些還未被選擇的元素，則在步驟300中，該方法依次從源列表中的未被選擇的元素中獲得一個元素，特別地，該方法獲得源列表中的緊接在前一元素之后的元素。

在步驟400中，執行二值搜索以搜索目標列表中的與源列表中選擇的元素匹配的元素，并且記錄找到的位置。然后，該過程返回步驟200以進一步確定源列表中的所有元素是否已被搜索。

當確定源列表中的所有元素已被搜索時，則該過程前進到步驟500，在該步驟中，所有找到的位置信息被獲得并且記錄為最終匹配結果。

下文，將參照圖3A至3F來描述應用二值搜索方法的示例。如圖3A中所示，選擇小尺寸列表作為源列表并選擇大尺寸列表作為目標列表，并且從源列表中選擇第一個元素、即起點“3”。然后，如圖3B所示，通過循環目標列表的整個范圍在目標列表中找到具有值“3”的元素。此后，由于在源列表中仍存在一些未被選擇的元素，因此如圖3C所示，從源列表中選擇源列表中的下一個元素，即“7”，并且如圖3D所示，仍通過循環目標列表的整個范圍在目標列表中找到具有值“7”的元素。應注意，對于第二個被選擇的元素的匹配處理仍是針對目標列表的整個范圍執行的，就如同第一個元素的情況下的處理那樣。這樣，源列表中的元素被依次選擇，并且對于源列表中的每個選擇的元素，均搜索目標列表的整個范圍以找到匹配元素，以便獲得最終匹配結果，如圖3E和3F所示。