技術領域

本發明涉及抽出局部對應(local?alignment)的局部對應抽出裝置，特別是涉及使用Smith-Waterman法來抽出局部對應的局部對應抽出裝置，所述局部對應是在兩個文件之間的類似的字符串對。

背景技術

在較長的文件之間，雖然文件整體相互類似的情況較為少見，但存在部分類似的情況。例如，可以考慮書籍之間的類似性。在書籍之間不是僅有一處類似位置，而是有多處類似位置的情況較多。若考慮在書籍之間由數個字符構成的詞語一致的情況，則在書籍之間的類似位置的數量會變得巨大。將在兩個文件之間的類似位置(類似字符串對)稱為局部對應。若能夠將該局部對應計數，則即使不讀取兩個文件的整體，也能夠通過僅讀取局部對應的周邊來把握兩個文件之間的類似性的依據。

例如，在專利審查等的審查業務中，必須判斷作為審查對象的申請與專利文獻或非專利文獻之間的內容的相同性及類似性。若能在作為判斷對象的文件之間將局部對應計數，則不必讀取文件整體，就能夠通過僅讀取局部對應的周邊判斷對象文件間的相同性及類似性，從而促進審查業務。

在概念檢索(similarity?seatch)中，在輸入字符串的情況下，按照類似度順序排序(ranking)并提示與輸入的字符串類似的文件。在這種情況下，用戶能夠從排序靠前的文件開始按順序調查與輸入的字符串匹配(relevant)的文件。但是，由于用戶難以了解排序的依據，為了判斷輸入的字符串與提示的文件的匹配性，必須閱讀提示的文件自身的情況較多。文件越長則閱讀理解時間也變長。

另一方面，在全文檢索(full?text?search)中，通過提示與輸入的字符串一致的字符串的周邊部來減少閱讀文件整體的工作。

因此，即使在概念檢索中，通過在輸入的字符串和與輸入的字符串匹配的文件之間抽出類似位置(局部對應)，并提示抽出的局部對應，能夠不閱讀文件整體就判斷文件的匹配性。

此外，若在專利申請的權利要求與說明書之間抽出局部對應，則能夠立即找到與權利要求相關的實施例。

作為抽出局部對應的現有技術存在有Smith-Waterman法(非專利文獻1)。Smith-Waterman法通過動態規劃法(dynamic?programming)高效地搜索分值(score)最大的局部對應。在此，分值是指部分字符串間的類似度。

通過抽出分值為規定值以上的局部對應，能夠從用于抽出局部對應而生成的分值矩陣中網羅性地(exhaustive)抽出更多的局部對應。然而，由于在該方法中單純地通過分值判斷是否為局部對應，導致也大量地抽出了包括已抽出的局部對應的周邊的無意義的字符的局部對應。因此，在局部對應中也需要取舍選擇出具有代表性(representative)的內容。換言之，代表性與網羅性雙方都需要滿足。

在專利文獻1中，記載有盡量不減少Smith-Waterman法的局部對應的抽出精度并提高局部對應的抽出效率的方法。具體而言，抽出完全一致的字符串對，并連結在抽出的字符串對中的在一定的間隔以內的字符串對。

專利文獻

專利文獻1：日本特開2004-038329號公報

非專利文獻

非專利文獻1：[Algorithms?on?Strings，Trees，and?Sequences](pp.232-234)，Gusfield，D.，Cambridge?University?Press，1997

發明要解決的問題

但是，在專利文獻1所記載的方法中，為了抽出完全一致的字符串對，必須預先制作后綴數組(suffix?array)等的索引。此外，專利文獻1所記載的方法的局部對應的抽出精度也低于Smith-Waterman法。用于遺傳基因序列的檢索的被稱為BLAST、FASTA的軟件也是與專利文獻1所記載的方法同樣地犧牲精度來實現高速化的方法，并且也必須預先制作索引。

由此，存在對于沒有進行索引化的數據就難以抽出局部對應的問題。

在沒有預先進行索引化的任意的長字符串之間抽出局部對應的情況下，難以網羅性地抽出具有代表性的局部對應。此外，若重視局部對應的網羅性則會損害代表性，若重視代表性則會損害網羅性。

發明內容

因此，本發明的目的在于，提供一種在沒有預先進行索引化的任意的字符串之間網羅性地抽出具有代表性的局部對應的局部對應抽出裝置。

用于解決問題的手段