(57)【特許請求の範囲】
【請求項１】
第１文字列及び第２文字列に対してそれぞれ単語分割を行なって、少なくとも一つの単語をそれぞれ含む第１シーケンス及び第２シーケンスを得るステップと、
予め定義した編集距離アルゴリズム、上記第１シーケンス及び上記第２シーケンスに基づいて、上記第１文字列と上記第２文字列との間の編集距離を特定するステップと、
上記編集距離、及び、上記第１シーケンスを上記第２シーケンスに変換するために行なった各操作の情報に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するステップと
を含み、
上記編集距離、及び、上記第１シーケンスを上記第２シーケンスに変換するために行なった各操作の情報に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するステップは、
上記第１シーケンスから上記第２シーケンスに変換するために行なった各操作情報の中の切替操作情報を取得するステップと、
上記各切替操作情報に基づいて、上記第１シーケンス及び上記第２シーケンスの両方の中に同時に存在する二つの単語の数である、ペアリングの数を特定するステップと、
上記編集距離、上記ペアリングの数、各操作の操作コスト、上記第１シーケンス中の単語の数、及び、上記第２シーケンス中の単語の数に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するステップと
を含むことを特徴とするプロセッサにより実行する類似性特定方法。
【請求項２】
上記各操作は、切替操作及び交換操作を含み、
上記編集距離、上記ペアリングの数、各操作の操作コスト、上記第１シーケンス中の単語の数、及び、上記第２シーケンス中の単語の数に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するステップは、
上記編集距離、上記ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、上記第１文字列と上記第２文字列との間の最小のセマンティックの編集距離を特定するステップと、
上記最小のセマンティックの編集距離を正規化して、正規化結果を得るステップと、
上記正規化結果に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するステップと
を含むことを特徴とする請求項１に記載の類似性特定方法。
【請求項３】
上記各操作は、切替操作、交換操作、挿入操作、削除操作の中の少なくとも一つを含み、
上記編集距離、上記ペアリングの数、各操作の操作コスト、上記第１シーケンス中の単語の数、及び、上記第２シーケンス中の単語の数に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するステップは、
上記編集距離、上記ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、上記第１文字列と上記第２文字列との間の第１セマンティックの編集距離を特定するステップと、
挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、上記第１シーケンス中の単語の数、及び、上記第２シーケンス中の単語の数に基づいて、上記第１文字列と上記第２文字列との間の第２セマンティックの編集距離を特定するステップと、
上記第１セマンティックの編集距離、及び、上記第２セマンティックの編集距離に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するステップと
を含むことを特徴とする請求項１に記載の類似性特定方法。
【請求項４】
切替操作と交換操作との間の関係に基づいて、切替操作の操作コスト及び交換操作の操作コストを特定するステップと、
切替操作、挿入操作、及び、削除操作の間の関係に基づいて、挿入操作の操作コスト、削除操作の操作コスト及び切替操作の操作コストを特定するステップと
をさらに含むことを特徴とする請求項１乃至３の中のいずれか１項に記載の類似性特定方法。
【請求項５】
切替操作と交換操作との間の関係に基づいて、２×切替操作の操作コスト＞交換操作の操作コストとして特定するステップと、
切替操作、挿入操作、及び、削除操作の間の関係に基づいて、挿入操作の操作コスト+削除操作の操作コスト＞切替操作の操作コストとして特定するステップと
をさらに含むことを特徴とする請求項４に記載の類似性特定方法。
【請求項６】
挿入操作と削除操作との間の関係に基づいて、挿入操作の操作コスト＝削除操作の操作コストとして特定するステップ
をさらに含むことを特徴とする請求項４に記載の類似性特定方法。
【請求項７】
予め定義した編集距離アルゴリズム、上記第１シーケンス及び上記第２シーケンスに基づいて、上記第１文字列と上記第２文字列との間の編集距離を特定するステップは、
予め定義した編集距離アルゴリズム、上記第１シーケンス及び上記第２シーケンスに基づいて、以下の式１に従って、上記第１文字列と上記第２文字列との間の編集距離を特定するステップを含み、
式１：minCost[i, j]=min(
minCost[i-1, j]+cost(S),
minCost[i, j-1]+cost(C),
minCost[i-1, j-1]+cost(T))
式１の中で、ｉは、第１シーケンス中のｉ番目の単語であり、ｊは、第２シーケンス中のｊ番目の単語であり、cost(S)は、削除操作の操作コストであり、cost(C)は、挿入操作の操作コストであり、cost(T)は、切替操作の操作コストである
ことを特徴とする請求項１に記載の類似性特定方法。
【請求項８】
上記編集距離、上記ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、上記第１文字列と上記第２文字列との間の最小のセマンティックの編集距離を特定するステップは、
上記編集距離、上記ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、以下の式２に従って、上記第１文字列と上記第２文字列との間の最小のセマンティックの編集距離を特定するステップを含み、
式２：minCost(S1, S2)=d-p(2cost(T)-cost(J))
式２の中で、S1及びS2は、それぞれ上記第１文字列及び上記第２文字列であり、minCost(S1, S2)は、上記最小のセマンティックの編集距離であり、ｄは、上記編集距離であり、ｐは、上記ペアリングの数であり、cost(J)は、上記交換操作の操作コストであり、cost(T)は、上記切替操作の操作コストであり、且つ、2cost(T)-cost(J)>0である
ことを特徴とする請求項２に記載の類似性特定方法。
【請求項９】
上記編集距離、上記ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、上記第１文字列と上記第２文字列との間の第１セマンティックの編集距離を特定するステップは、
上記編集距離、上記ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、以下の式３に従って、上記第１文字列と上記第２文字列との間の第１セマンティックの編集距離を特定するステップを含み、
式３：minCost(S1, S2)=d-p(2cost(T)-cost(J))
式３の中で、S1及びS2は、それぞれ上記第１文字列及び上記第２文字列であり、minCost(S1, S2)は、上記第１セマンティックの編集距離であり、ｄは、上記編集距離であり、ｐは、上記ペアリングの数であり、cost(J)は、上記交換操作の操作コストであり、cost(T)は、上記切替操作の操作コストであり、且つ、2cost(T)-cost(J)>0である
ことを特徴とする請求項３に記載の類似性特定方法。
【請求項１０】
上記挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、上記第１シーケンス中の単語の数、及び、上記第２シーケンス中の単語の数に基づいて、上記第１文字列と上記第２文字列との間の第２セマンティックの編集距離を特定するステップは、
挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、上記第１シーケンス中の単語の数、及び、上記第２シーケンス中の単語の数に基づいて、以下の式４に従って、上記第１文字列と上記第２文字列との間の第２セマンティックの編集距離を特定するステップを含み、
式４：normFact(S1, S2)=min(n, m)cost(T)+(max(n, m)-min(n, m))×costM
costM=cost(C),  if n<m
costM=cost(S),  if n>m
式４の中で、normFact(S1, S2)は、上記第２セマンティックの編集距離であり、ｎは、上記第１シーケンスの単語の数であり、ｍは、上記第２シーケンスの単語の数であり、cost(T)は、上記切替操作の操作コストであり、cost(S)は、上記削除操作の操作コストであり、cost(C)は、上記挿入操作の操作コストである
ことを特徴とする請求項３に記載の類似性特定方法。
【請求項１１】
上記第１セマンティックの編集距離、及び、上記第２セマンティックの編集距離に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するステップは、
上記第１セマンティックの編集距離、及び、上記第２セマンティックの編集距離に基づいて、以下の式５に従って、上記第１文字列と上記第２文字列との間の類似性を特定するステップを含み、
式５：sim(S1, S2)=1-minCost(S1, S2)/normFact(S1, S2)
式５の中で、sim(S1, S2)は、上記第１文字列と上記第２文字列との間の類似性であり、minCost(S1, S2)は、上記第１セマンティックの編集距離であり、normFact(S1, S2)は、上記第２セマンティックの編集距離である
ことを特徴とする請求項３に記載の類似性特定方法。
【請求項１２】
第１文字列及び第２文字列に対してそれぞれ単語分割を行なって、少なくとも一つの単語をそれぞれ含む第１シーケンス及び第２シーケンスを得るための単語分割モジュールと、
予め定義した編集距離アルゴリズム、上記第１シーケンス及び上記第２シーケンスに基づいて、上記第１文字列と上記第２文字列との間の編集距離を特定するための第１特定モジュールと、
上記編集距離、及び、上記第１シーケンスを上記第２シーケンスに変換するために行なった各操作の情報に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するための第２特定モジュールと
を備え、
上記第２特定モジュールは、
上記第１シーケンスから上記第２シーケンスに変換するために行なった各操作情報の中の切替操作情報を取得するための取得ユニットと、
上記各切替操作情報に基づいて、上記第１シーケンス及び上記第２シーケンスの両方の中に同時に存在する二つの単語の数である、ペアリングの数を特定するための第１特定ユニットと、
上記編集距離、上記ペアリングの数、各操作の操作コスト、上記第１シーケンス中の単語の数、及び、上記第２シーケンス中の単語の数に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するための第２特定ユニットと
を備えることを特徴とする類似性特定装置
【請求項１３】
上記各操作は、切替操作及び交換操作を含み、上記第２特定ユニットは、
上記編集距離、上記ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、上記第１文字列と上記第２文字列との間の最小のセマンティックの編集距離を特定するための第１特定サブユニットと、
上記最小のセマンティックの編集距離を正規化して、正規化結果を得るための正規化サブユニットと、
上記正規化結果に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するための第２特定サブユニットと
を備えることを特徴とする請求項１２に記載の類似性特定装置
【請求項１４】
上記各操作は、切替操作、交換操作、挿入操作、削除操作の中の少なくとも一つを含み、上記第２特定ユニットは、
上記編集距離、上記ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、上記第１文字列と上記第２文字列との間の第１セマンティックの編集距離を特定するための第３特定サブユニットと、
挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、上記第１シーケンス中の単語の数、及び、上記第２シーケンス中の単語の数に基づいて、上記第１文字列と上記第２文字列との間の第２セマンティックの編集距離を特定するための第４特定サブユニットと、
上記第１セマンティックの編集距離、及び、上記第２セマンティックの編集距離に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するための第５特定サブユニットと
を備えることを特徴とする請求項１２に記載の類似性特定装置
【請求項１５】
切替操作と交換操作との間の関係に基づいて、切替操作の操作コスト及び交換操作の操作コストを特定するための第３特定モジュールと、
切替操作、挿入操作、及び、削除操作の間の関係に基づいて、挿入操作の操作コスト、削除操作の操作コスト及び切替操作の操作コストを特定するための第４特定モジュールと
をさらに備えることを特徴とする請求項１２乃至１４の中のいずれか１項に記載の類似性特定装置
【請求項１６】
切替操作と交換操作との間の関係に基づいて、２×切替操作の操作コスト＞交換操作の操作コストとして特定するための第５特定モジュールと、
切替操作、挿入操作、及び、削除操作の間の関係に基づいて、挿入操作の操作コスト+削除操作の操作コスト＞切替操作の操作コストとして特定するための第６特定モジュールと
をさらに備えることを特徴とする請求項１５に記載の類似性特定装置
【請求項１７】
挿入操作と削除操作との間の関係に基づいて、挿入操作の操作コスト＝削除操作の操作コストとして特定するための第７特定モジュール
をさらに備えることを特徴とする請求項１５に記載の類似性特定装置
【請求項１８】
上記第１特定モジュールは、予め定義した編集距離アルゴリズム、上記第１シーケンス及び上記第２シーケンスに基づいて、以下の式１に従って、上記第１文字列と上記第２文字列との間の編集距離を特定し、
式１：minCost[i, j]=min(
minCost[i-1, j]+cost(S),
minCost[i, j-1]+cost(C),
minCost[i-1, j-1]+cost(T))
式１の中で、ｉは、上記第１シーケンス中のｉ番目の単語であり、ｊは、上記第２シーケンス中のｊ番目の単語であり、cost(S)は、削除操作の操作コストであり、cost(C)は、挿入操作の操作コストであり、cost(T)は、切替操作の操作コストである
ことを特徴とする請求項１２に記載の類似性特定装置
【請求項１９】
上記第１特定サブユニットは、上記編集距離、上記ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、以下の式２に従って、上記第１文字列と上記第２文字列との間の最小のセマンティックの編集距離を特定し、
式２：minCost(S1, S2)=d-p(2cost(T)-cost(J))
式２の中で、S1及びS2は、それぞれ上記第１文字列及び上記第２文字列であり、minCost(S1, S2)は、上記最小のセマンティックの編集距離であり、ｄは、上記編集距離であり、ｐは、上記ペアリングの数であり、cost(J)は、上記交換操作の操作コストであり、cost(T)は、上記切替操作の操作コストであり、且つ、2cost(T)-cost(J)>0である
ことを特徴とする請求項１３に記載の類似性特定装置
【請求項２０】
上記第３特定サブユニットは、上記編集距離、上記ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、以下の式３に従って、上記第１文字列と上記第２文字列との間の第１セマンティックの編集距離を特定し、
式３：minCost(S1, S2)=d-p(2cost(T)-cost(J))
式３の中で、S1及びS2は、それぞれ上記第１文字列及び上記第２文字列であり、minCost(S1, S2)は、上記第１セマンティックの編集距離であり、ｄは、上記編集距離であり、ｐは、上記ペアリングの数であり、cost(J)は、上記交換操作の操作コストであり、cost(T)は、上記切替操作の操作コストであり、且つ、2cost(T)-cost(J)>0である
ことを特徴とする請求項１４に記載の類似性特定装置
【請求項２１】
第４特定サブユニットは、挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、上記第１シーケンス中の単語の数、及び、上記第２シーケンス中の単語の数に基づいて、以下の式４に従って、上記第１文字列と上記第２文字列との間の第２セマンティックの編集距離を特定し、
式４：normFact(S1, S2)=min(n, m)cost(T)+(max(n, m)-min(n, m))×costM
costM=cost(C),  if n<m
costM=cost(S),  if n>m
式４の中で、normFact(S1, S2)は、上記第２セマンティックの編集距離であり、ｎは、上記第１シーケンスの単語の数であり、ｍは、上記第２シーケンスの単語の数であり、cost(T)は、上記切替操作の操作コストであり、cost(S)は、上記削除操作の操作コストであり、cost(C)は、上記挿入操作の操作コストである
ことを特徴とする請求項１４に記載の類似性特定装置
【請求項２２】
上記第５特定サブユニットは、上記第１セマンティックの編集距離、及び、上記第２セマンティックの編集距離に基づいて、以下の式５に従って、上記第１文字列と上記第２文字列との間の類似性を特定し、
式５：sim(S1, S2)=1-minCost(S1, S2)/normFact(S1, S2)
式５の中で、sim(S1, S2)は、上記第１文字列と上記第２文字列との間の類似性であり、minCost(S1, S2)は、上記第１セマンティックの編集距離であり、normFact(S1, S2)は、上記第２セマンティックの編集距離である
ことを特徴とする請求項１４に記載の類似性特定装置
【請求項２３】
プロセッサと、
前記プロセッサが実行可能な命令を記憶するためのメモリと
を備え、
前記プロセッサは、
第１文字列及び第２文字列に対してそれぞれ単語分割を行なって、少なくとも一つの単語をそれぞれ含む第１シーケンス及び第２シーケンスを得るし、
予め定義した編集距離アルゴリズム、上記第１シーケンス及び上記第２シーケンスに基づいて、上記第１文字列及び上記第２文字列との間の編集距離を特定し、
上記編集距離、及び、上記第１シーケンスを上記第２シーケンスに変換するために行なった各操作の情報に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するように構成され、
上記編集距離、及び、上記第１シーケンスを上記第２シーケンスに変換するために行なった各操作の情報に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定することは、
上記第１シーケンスから上記第２シーケンスに変換するために行なった各操作情報の中の切替操作情報を取得し、
上記各切替操作情報に基づいて、上記第１シーケンス及び上記第２シーケンスの両方の中に同時に存在する二つの単語の数である、ペアリングの数を特定し、
上記編集距離、上記ペアリングの数、各操作の操作コスト、上記第１シーケンス中の単語の数、及び、上記第２シーケンス中の単語の数に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するように構成される
ことを特徴とする端末。
【請求項２４】
プロセッサに実行されることにより、請求項１から請求項１１のいずれか１項に記載の類似性特定方法を実現することを特徴とするプログラム。
【請求項２５】
請求項２４に記載のプログラムが記録された記録媒体。
【発明の詳細な説明】
【相互参照】
【０００１】
本願は、出願番号がＣＮ２０１５１０８８２４６８.２であって、出願日が２０１５年１２月０３日である中国特許出願に基づいて優先権を主張し、当該中国特許出願のすべての内容を援用する。
【技術分野】
【０００２】
本発明は、自然言語処理分野に関し、特に、類似性特定方法、装置、端末、プログラム及び記録媒体に関する。
【背景技術】
【０００３】
自然言語処理分野において、文字列同士の間の類似性を特定する方法は、一つの基本的な問題であり、テキストのクラスタリング、情報検索、等のような、多くの場面に適用される。このため、文字列同士の間の類似性をどのように特定するのかは、研究者たちに幅広く注目されている。
【０００４】
関連技術で、文字列同士の間の類似性を特定する時に、二つの文字列の間の編集距離を算出して実現する。具体的に、これら二つの文字列をそれぞれ単語分割して各文字を得た後に、一つの文字列中の文字に対して、削除操作、挿入操作、及び切替操作を行なって、一つの文字列をもう一つの文字列に変換し、続いて、一つの文字列からもう一つの文字列に変換するのにかかる最小の操作回数を算出して、当該最小の操作回数を、これら二つの文字列同士の間の編集距離として、編集距離に基づいてこれら二つの文字列同士の間の類似性を算出する。
【発明の概要】
【０００５】
本発明は、類似性特定方法、装置、端末、プログラム及び記録媒体を提供する。
【０００６】
本発明の実施例に係る第１の態様によると、類似性特定方法を提供する。
【０００７】
上記方法は、
第１文字列及び第２文字列に対してそれぞれ単語分割を行なって、少なくとも一つの単語をそれぞれ含む第１シーケンス及び第２シーケンスを得るステップと、
予め定義した編集距離アルゴリズム、上記第１シーケンス及び上記第２シーケンスに基づいて、上記第１文字列と上記第２文字列との間の編集距離を特定するステップと、
上記編集距離、及び、上記第１シーケンスを上記第２シーケンスに変換するために行なった各操作の情報に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するステップと
を含む。
【０００８】
本発明の実施例に係る第２の態様によると、類似性特定装置を提供する。
【０００９】
上記装置は、
第１文字列及び第２文字列に対してそれぞれ単語分割を行なって、少なくとも一つの単語をそれぞれ含む第１シーケンス及び第２シーケンスを得るための単語分割モジュールと、
予め定義した編集距離アルゴリズム、上記第１シーケンス及び上記第２シーケンスに基づいて、上記第１文字列と上記第２文字列との間の編集距離を特定するための第１特定モジュールと、
上記編集距離、及び、上記第１シーケンスを上記第２シーケンスに変換するために行なった各操作の情報に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するための第２特定モジュールと
を備える。
【００１０】
本発明の実施例に係る第３の態様によると、端末を提供する。
【００１１】
上記端末は、
プロセッサと、
前記プロセッサが実行可能な命令を記憶するためのメモリと
を備え、
前記プロセッサは、
第１文字列及び第２文字列に対してそれぞれ単語分割を行なって、少なくとも一つの単語をそれぞれ含む第１シーケンス及び第２シーケンスを得るし、
予め定義した編集距離アルゴリズム、上記第１シーケンス及び上記第２シーケンスに基づいて、上記第１文字列及び上記第２文字列との間の編集距離を特定し
上記編集距離、及び、上記第１シーケンスを上記第２シーケンスに変換するために行なった各操作の情報に基づいて、上記第１文字列と上記第２文字列との間の類似性を特定するように構成される。
本発明の実施例の第４の態様によると、プログラムを提供し、当該プログラムは、プロセッサに実行されることにより、上記の類似性特定方法を実現する。
本発明の実施例の第５の態様によると、記録媒体を提供し、当該記録媒体には、上記プログラムが記録されている。
【００１２】
本発明の実施例が提供する構成の有益な効果は以下のとおりである。
【００１３】
第１文字列及び第２文字列を、それぞれ、第１シーケンス及び第２シーケンスに単語分割して、第１文字列から第２文字列に変換する時の編集距離を特定する時に、第１文字列及び第２文字列の中の各文字に基づいて実現するのではなく、第１シーケンス及び第２シーケンスの中の各単語に基づいて実現する。ここで、文字列の中の各単語は少なくとも一つの文字を含む可能があるため、編集距離に基づいて類似性を特定する時に、文字列の中の各文字同士との間の関連関係を組み合わせたので、特定した類似性がもっと正確になる。
【００１４】
以上の統括な記述と以下の細部記述は、ただ例示的なものであり、本発明を制限するものではないと、理解するべきである。
【図面の簡単な説明】
【００１５】
ここでの図面は、明細書に合併されて本明細書の一部を構成して本発明に合致する実施例を示し、明細書とともに本発明の原理の説明するに用いられる。
【００１６】
【図１】例示的な一実施例に係る類似性特定方法を示すフローチャートである。
【図２】例示的な一実施例に係る類似性特定方法を示すフローチャートである。
【図３】例示的な一実施例に係る類似性特定装置を示すブロック図である。
【図４】例示的な一実施例に係る第２特定モジュールを示すブロック図である。
【図５】例示的な一実施例に係る第２特定ユニットを示すブロック図である。
【図６】例示的な一実施例に係る第２特定ユニットを示すブロック図である。
【図７】例示的な一実施例に係る類似性特定装置を示すブロック図である。
【図８】例示的な一実施例に係る類似性特定装置を示すブロック図である。
【図９】例示的な一実施例に係る類似性特定装置を示すブロック図である。
【図１０】例示的な一実施例に係る端末を示すブロック図である。
【図１１】例示的な一実施例に係るサーバを示すブロック図である。
【発明を実施するための形態】
【００１７】
ここで、例示的な実施例を詳細に説明する。また、説明中の例は、図面に示している。以下の記述において、図面を説明する際に特に説明しない場合、異なる図面中の同一の符号は、同一或は同様な要素を意味する。以下の例示的な実施例において記述する実施方法は、本発明に合致するすべての実施方法を代表しない。逆に、それらは、添付の特許請求の範囲において詳細に記述された、本発明のいくつかの態様と合致する装置、及び方法の例に過ぎない。
【００１８】
自然言語処理分野において、文字列同士の間の類似性を特定する方法は、一つの基本的な問題であり、テキストのクラスタリング、情報検索、等のような、多くの場面に適用される。本発明の実施例は、特定する二つの文字列同士の間の類似性をもっと正確にするために、類似性特定方法を提供する。図１は、例示的な一実施例に係る類似性特定方法を示すフローチャートである。本発明の実施例によって提供する類似性特定方法は、端末に適用される。図１に示したように、本発明の実施例によって提供する類似性特定方法は、以下のステップを含む。
【００１９】
ステップＳ１０１において、第１文字列及び第２文字列に対してそれぞれ単語分割を行なって、少なくとも一つの単語がそれぞれ含まれた第１シーケンス及び第２シーケンスを得る。
【００２０】
ステップＳ１０２において、予め定義した編集距離アルゴリズム、第１シーケンス、及び第２シーケンスに基づいて、第１文字列及び第２文字列との間の編集距離を特定する。
【００２１】
ステップＳ１０３において、編集距離、及び、第１シーケンスから第２シーケンスに変換するために行う各操作の情報に基づいて、第１文字列と第２文字列との間の類似性を特定する。
【００２２】
本発明の実施例によって提供する方法によると、第１文字列及び第２文字列を、それぞれ、第１シーケンス及び第２シーケンスに単語分割して、第１文字列から第２文字列に変換する時の編集距離を特定する時に、第１文字列及び第２文字列の中の各文字に基づいて実現するのではなく、第１シーケンス及び第２シーケンスの中の各単語に基づいて実現する。ここで、文字列の中の各単語は少なくとも一つの文字を含む可能があるため、編集距離に基づいて類似性を特定する時に、文字列の中の各文字同士との間の関連関係を組み合わせたので、特定した類似性がもっと正確になる。
【００２３】
もう一実施例において、編集距離、及び、第１シーケンスから第２シーケンスに変換するために行う各操作の情報に基づいて、第１文字列と第２文字列との間の類似性を特定するステップは、
第１シーケンスから第２シーケンスに変換するために行う各操作情報の中の切替操作情報を取得するステップと、
各切替操作情報に基づいて、第１シーケンス及び第２シーケンスの両方の中に同時に存在する二つの単語の数である、ペアリングの数を特定するステップと、
編集距離、ペアリングの数、各操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の類似性を特定するステップと
を含む。
【００２４】
もう一実施例において、各操作包括は、切替操作、及び、交換操作を含み、
編集距離、ペアリングの数、各操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の類似性を特定するステップは、
編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、第１文字列と第２文字列との間の最小のセマンティックの編集距離を特定するステップと、
最小のセマンティックの編集距離を正規化して、正規化結果を得るステップと、
正規化結果に基づいて、第１文字列と第２文字列との間の類似性を特定するステップと
を含む。
【００２５】
もう一実施例において、各操作は、切替操作、及び、交換操作、挿入操作、及び、削除操作の中の少なくとも一つを含み、
編集距離、ペアリングの数、各操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の類似性を特定するステップは、
編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、第１文字列と第２文字列との間の第１セマンティックの編集距離を特定するステップと、
挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の第２セマンティックの編集距離を特定するステップと、
第１セマンティックの編集距離、及び、第２セマンティックの編集距離に基づいて、第１文字列と第２文字列との間の類似性を特定するステップと
を含む。
【００２６】
もう一実施例において、当該方法は、
切替操作と交換操作との間の関係に基づいて、切替操作の操作コスト及び交換操作の操作コストを特定するステップと、
切替操作、挿入操作、及び、削除操作の間の関係に基づいて、挿入操作の操作コスト、削除操作の操作コスト及び切替操作の操作コストを特定するステップと
をさらに含む。
【００２７】
もう一実施例において、当該方法は、
切替操作と交換操作との間の関係に基づいて、２×切替操作の操作コスト＞交換操作の操作コストとして特定するステップと、
切替操作、挿入操作、及び、削除操作の間の関係に基づいて、挿入操作の操作コスト+削除操作の操作コスト＞切替操作の操作コストとして特定するステップと
をさらに含む。
【００２８】
もう一実施例において、当該方法は、
挿入操作と削除操作との間の関係に基づいて、挿入操作の操作コスト＝削除操作の操作コストとして特定するステップ
をさらに含む。
【００２９】
もう一実施例において、予め定義した編集距離アルゴリズム、第１シーケンス、及び第２シーケンスに基づいて、第１文字列及び第２文字列との間の編集距離を特定するステップは、
予め定義した編集距離アルゴリズム、第１シーケンス、及び第２シーケンスに基づいて、以下の式１に従って、第１文字列及び第２文字列との間の編集距離を特定するステップを含み、
式１：minCost[i, j]=min(
minCost[i-1, j]+cost(S),
minCost[i, j-1]+cost(C),
minCost[i-1, j-1]+cost(T))
式１の中で、ｉは、第１シーケンス中のｉ番目の単語であり、ｊは、第２シーケンス中のｊ番目の単語であり、cost(S)は、削除操作の操作コストであり、cost(C)は、挿入操作の操作コストであり、cost(T)は、切替操作の操作コストである。
【００３０】
もう一実施例において、編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、第１文字列と第２文字列との間の最小のセマンティックの編集距離を特定するステップは、
編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、以下の式２に従って、第１文字列と第２文字列との間の最小のセマンティックの編集距離を特定するステップを含み、
式２：minCost(S1, S2)=d-p(2cost(T)-cost(J))
式２の中で、S1及びS2は、それぞれ第１文字列及び第２文字列であり、minCost(S1, S2)は、最小のセマンティックの編集距離であり、ｄは、編集距離であり、ｐは、ペアリングの数であり、cost(J)は、交換操作の操作コストであり、cost(T)は、切替操作の操作コストであり、且つ、2cost(T)-cost(J)>0である。
【００３１】
もう一実施例において、編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、第１文字列と第２文字列との間の第１セマンティックの編集距離を特定するステップは、
編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、以下の式３に従って、第１文字列と第２文字列との間の第１セマンティックの編集距離を特定するステップを含み、
式３：minCost(S1, S2)=d-p(2cost(T)-cost(J))
式３の中で、S1及びS2は、それぞれ第１文字列及び第２文字列であり、minCost(S1, S2)は、第１セマンティックの編集距離であり、ｄは、編集距離であり、ｐは、ペアリングの数であり、cost(J)は、交換操作の操作コストであり、cost(T)は、切替操作の操作コストであり、且つ、2cost(T)-cost(J)>0である。
【００３２】
もう一実施例において、挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の第２セマンティックの編集距離を特定するステップは、
挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、以下の式４に従って、第１文字列と第２文字列との間の第２セマンティックの編集距離を特定するステップを含み、
式４：normFact(S1, S2)=min(n, m)cost(T)+(max(n, m)-min(n, m))×costM
costM=cost(C),  if n<m
costM=cost(S),  if n>m
式４の中で、normFact(S1, S2)は、第２セマンティックの編集距離であり、ｎは、第１シーケンスの単語の数であり、ｍは、第２シーケンスの単語の数であり、cost(T)は、切替操作の操作コストであり、cost(S)は、削除操作の操作コストであり、cost(C)は、挿入操作の操作コストである。
【００３３】
もう一実施例において、第１セマンティックの編集距離、及び、第２セマンティックの編集距離に基づいて、第１文字列と第２文字列との間の類似性を特定するステップは、
第１セマンティックの編集距離、及び、第２セマンティックの編集距離に基づいて、以下の式５に従って、第１文字列と第２文字列との間の類似性を特定するステップを含み、
式５：sim(S1, S2)=1-minCost(S1, S2)/normFact(S1, S2)
式５の中で、sim(S1, S2)は、第１文字列と第２文字列との間の類似性であり、minCost(S1, S2)は、第１セマンティックの編集距離であり、normFact(S1, S2)は、第２セマンティックの編集距離である。
【００３４】
上記の全てのオプション的な構成を、任意の組合せによって、本発明のオプション的な実施例を実現することができ、ここでは繰り返して説明しない。
【００３５】
図２は、例示的な一実施例に係る類似性特定方法を示すフローチャートである。当該類似性特定方法は、端末に適用される。図２に示したように、本発明の実施例によって提供する類似性特定方法は、以下のステップを含む。
【００３６】
ステップＳ２０１において、第１文字列及び第２文字列に対してそれぞれ単語分割を行なって、第１シーケンス及び第２シーケンスを得る。
【００３７】
文字列の中の各文字同士の間は、完全に独立したのではなく、一定の関連関係を有する可能がある。即ち、ある隣接する二つの文字は、分割できない一つの整体である可能がある。例えば、「今日、私は香山を登る」の中の「今日」及び「香山を」は、それぞれ、分割できない一つの整体である。このため、本発明の実施例は、二つの文字列同士の間の類似性を特定する時に、二つの文字列をそれぞれ各文字に単語分割するのではなく、二つの文字列を単語分割して、各文字列を各単語に単語分割し、単語分割された後の文字列は少なくとも一つの単語を含む。説明の便利のために、本発明の実施例は、類似性を特定しようとする二つの文字列を、それぞれ、第１文字列及び第２文字列として定義し、且つ、第１文字列を各単語に単語分割した後に、第１シーケンスを得るし、第２文字列を各単語に単語分割した後に、第２シーケンスを得る。ここで、第１シーケンス及び第２シーケンスは、それぞれ、少なくとも一つの単語を含む。
【００３８】
例えば、第１文字列及び第２文字列が、それぞれ、Ｓ１及びＳ２であると、第１シーケンス及び第２シーケンスは、それぞれ、（Ｓ１１, Ｓ１２, Ｓ１３、… 、Ｓ１ｎ）及び（Ｓ２１, Ｓ２２, Ｓ２３、… 、Ｓ２ｍ）である。ここで、Ｓ１の中の単語の数はｎであり、Ｓ２の中の単語の数はｍである。
【００３９】
本発明の実施例においては、第１文字列及び第２文字列の言語に対して、具体的に、限定しない。例えば、第１文字列及び第２文字列は、中国語、或は、英語等である。ここで、第１文字列及び第２文字列は、それぞれ、一つのセンテンスであってもよい。例えば、第１文字列は、”今日、私は香山を登る”であり、第２文字列は、”私は、今日香山を登る”である。
【００４０】
ステップＳ２０２において、切替操作と交換操作との間の関係に基づいて、切替操作の操作コスト及び交換操作の操作コストを特定し、切替操作、挿入操作、及び、削除操作の間の関係に基づいて、挿入操作の操作コスト、削除操作の操作コスト及び切替操作の操作コストを特定する。
【００４１】
従来の文字列同士の間の類似性を特定する方法によると、一つの文字列をもう一つの文字列に変換する時に、一般的に、挿入操作、削除操作及び切替操作のような３種の編集操作があり、且つ、これら３種の操作の操作コストは同一である。しかし、文字列の中で、ある成分が文字列の中の互いに異なる位置に出現する時に、文字列全体の意味は、変わらない。例えば、「今日、私は香山に行くつもりである」、「私は、今日香山に行くつもりである」、及び、「私のつもりは、今日、香山に行く」の中で、各単語の文字列の中の位置が互いに異なるが、これら三つの文字列の意味は、同一である。このため、本発明の実施例において、従来の挿入操作、削除操作及び切替操作を基に、交換操作を新たに定義し、また、各操作同士の間の関係に基づいて、互いに異なる操作に対して、互いに異なる操作コストを定義した。
【００４２】
本発明の実施例においては、各操作に割り当てる操作コストの具体的な数値にたいして、具体的に、限定しない。しかし、本発明の実施例においては、具体的に実施する時に、交換操作を２回の切替操作に分解できるため、切替操作と交換操作との間の関係に基づいて、切替操作コスト及び交換操作コストを特定できる。例えば、本発明の実施例で定義する切替操作コストと交換操作コストとの間の関係は、“２×切替操作の操作コスト＞交換操作の操作コスト”を満たす。
即ち、2cost(T)-cost(J)>0。
ここで、cost(T)は、切替操作の操作コストである、cost(J)は、交換操作の操作コストである。
【００４３】
また、本発明の実施例においては、１回の切替操作を、１回の削除操作及び１回の挿入操作に分解できるため、切替操作、挿入操作、及び、削除操作の間の関係に基づいて、挿入操作コスト及び削除操作コストを特定できる。例えば、本発明の実施例で定義する切替操作コスト、交換操作コスト及び削除操作コストとの間の関係は、「挿入操作の操作コスト+削除操作の操作コスト＞切替操作の操作コスト」を満たす。さらに、「切替操作の操作コストは、挿入操作の操作コスト及び削除操作の操作コストの中の最大値より大きい」と特定する。一例として、このような関係は、以下の式のとおりである。
max(cost(C), cost(S)) < cost(T) < cost(C)+cost(S)。
ここで、cost(S)は、削除操作の操作コストであり、cost(C)は、挿入操作の操作コストである。
【００４４】
なお、類似性に対称性があれば、即ち、第１文字列の中に一つの文字を挿入することが、第２文字列の中から一つの文字を削除することと、等しいであれば、挿入操作と削除操作との間の関係に基づいて、「挿入操作コスト＝削除操作コスト」を特定できる。当然ながら、類似性に対称性がない情況に対して、挿入操作コストが削除操作コストと等しくないか、或いは、等しいと定義してもよく、本発明の実施例においては、これに対して、具体的に、限定しない。
【００４５】
ステップＳ２０３において、切替操作の操作コスト、削除操作の操作コスト及び挿入操作の操作コストに基づいて、予め定義した編集距離アルゴリズムを生成する。
【００４６】
一例として、予め定義した編集距離アルゴリズムは、以下の式１のとおりである。
式１：minCost[i, j]=min(
minCost[i-1, j]+cost(S),
minCost[i, j-1]+cost(C),
minCost[i-1, j-1]+cost(T))
式１の中で、ｉは、第１シーケンス中のｉ番目の単語であり、ｊは、第２シーケンス中のｊ番目の単語であり、cost(S)は、削除操作の操作コストであり、cost(C)は、挿入操作の操作コストであり、cost(T)は、切替操作の操作コストである。
【００４７】
当該式１から分かるように、本発明の実施例の予め定義した編集距離アルゴリズムは、動的計画法アルゴリズムである。当該予め定義した編集距離アルゴリズムは、本発明の実施例において予め定義した削除操作の操作コスト、挿入操作の操作コスト及び切替操作の操作コストに基づいて得たものである。
【００４８】
ステップＳ２０２及びステップＳ２０３は、類似性を特定する前に実行すべきなステップであり、二つの文字列同士の間の類似性を特定する度に実行すべきなステップではなく、類似性を特定する前に、各操作の操作コスト及び予め定義した編集距離アルゴリズムを既に特定したことを保証するためのステップであることを、説明する必要がある。
【００４９】
ステップＳ２０４において、予め定義した編集距離アルゴリズム、第１シーケンス、及び第２シーケンスに基づいて、第１文字列及び第２文字列との間の編集距離を特定する。
【００５０】
二つの文字列同士の間の編集距離とは、その中の一つの文字列をもう一つの文字列に変換するのにかかる最少の編集操作回数である。ここで、各種の編集操作は、それぞれ、一つの操作コストに対応されるため、変換する時の合計の操作コストを、編集距離とする。本発明の実施例において、文字列同士の間の変換を行う時に、行うことができる編集操作は、切替操作、挿入操作、削除操作及び交換操作を含む。
【００５１】
本発明の実施例においては、上記の式１によって予め定義した編集距離アルゴリズムに組み合わせて、予め定義した編集距離アルゴリズム、第１シーケンス、及び第２シーケンスに基づいて、第１文字列と第２文字列との間の編集距離を特定した後に、予め定義した編集距離アルゴリズム、第１シーケンス、及び第２シーケンスに基づいて、上記の式１に従って、第１文字列と第２文字列との間の編集距離を算出できる。式１の編集距離を算出する具体的な原理は、従来の動的計画法アルゴリズムによって編集距離を算出する原理と同一であり、本発明の実施例においては、これに対して詳細に説明しない。
【００５２】
ステップＳ２０５において、編集距離、及び、第１シーケンスから第２シーケンスに変換するために行う各操作の情報に基づいて、第１文字列と第２文字列との間の類似性を特定する。
【００５３】
本発明の実施例において、第１シーケンスから第２シーケンスに変換するために行なった各操作の情報は、操作の種類、各種類の操作の操作回数、及び、各種類の操作の操作コストを含む。
【００５４】
本発明の実施例においては、互いに異なる操作に対して互いに異なる操作コストを予め定義したので、二つの文字列同士の間の編集距離に対する定義に組み合わると、第１文字列から第２文字列に変換するのにかかる各操作の操作コストは、編集距離に直接影響を及ぼす。このため、第１文字列と第２文字列との間の類似性を特定する時に、編集距離、及び、編集距離を得るために行なった各操作の操作情報に基づいて、特定する。操作情報は、操作コストを含み、編集距離を得る時の各操作の操作コストは、ステップＳ２０２において予め設定されている。
【００５５】
例えば、第１文字列から第２文字列に変換する時に行なった操作が、２回の挿入操作、１回の削除操作、１回の交換操作、及び、１回の切替操作を含むと、第１文字列及び第２文字列との間の編集距離ｄは、d=2cost(C)+cost(S))+cost(T)+cost(J)である。この時、第１文字列と第２文字列との間の類似性を特定する時に、編集距離、挿入操作の操作コスト、削除操作の操作コスト、交換操作の操作コスト、及び、切替操作の操作コストに基づいて、特定する。
【００５６】
一例として、編集距離、及び、第１シーケンスから第２シーケンスに変換するために行う各操作の情報に基づいて、第１文字列と第２文字列との間の類似性を特定する時に、以下のステップＳ２０５１乃至ステップＳ２０５３によって実現するが、これらに限定されない。
【００５７】
ステップＳ２０５１において、編集距離を得る時に、第１シーケンスから第２文字列に変換する時に行なった各操作情報の中の切替操作情報を取得する。
【００５８】
切替操作とは、第１文字列の中のある一つの単語をもう一つの単語に切り替える操作である。本発明の実施例においては、編集距離を特定する同時に、変換過程において行なった各切替操作の情報を統計して、各切替操作の情報を、指定された集合中に記録する。ここで、切替操作の情報は、切替操作の被切替単語、及び、被切替単語のシーケンス中の位置を含む。このため、当該指定された集合中に記録するデータは、被切替単語、及び、被切替単語の第１シーケンス中の位置を含む。例えば、第１文字列が「私は今日香山に行くつもりである」であり、第１シーケンスが「私は−今日−香山に−行く−つもりである」であり、且つ、被切替単語が「香山に」及び「つもりである」であると、指定された集合中に記録する切替操作の情報は、「香山に−３、つもりである−５」である。このため、指定された集合の中から編集距離を取得する時に、第１文字列から第２文字列に変換する時に行なった各操作情報の中の切替操作情報を得ることができ、具体的には、各切替操作の被切替単語、及び、各被切替単語の第１シーケンス中の位置を得ることができる。
【００５９】
なお、本発明の実施例において、切替操作と交換操作との間の関係に基づいて、交換操作を新たに定義し、且つ、2cost(T)-cost(J)>0を予め定義したため、２回の切替操作のコストが１回の交換操作のコストより大きいことが分かる。このため、もし、第１文字列を第２文字列に変換する時に、１回の交換操作によって実現できれば、２回の切替操作によって実現しない。このため、指定された集合中に、第１シーケンス中の被切替単語、及び、各被切替単語の第１シーケンス中の位置を記録するほか、さらに、指定された集合中の任意の二つの単語が第２シーケンス中に存在するか否かを、特定する。もし、任意の二つの単語が第２シーケンス中に存在すると、指定された集合中に、さらに、これら二つの単語及び各単語の第２シーケンス中の位置を記録する。
【００６０】
例えば、第１文字列が「私は、今日香山に行くつもりである」であり、第１シーケンスが「私は−今日−香山に−行く−つもりである」であり、且つ、被切替単語が「香山」及び「つもりである」であり、第２文字列が「今日、私は香山に行くつもりである」であり、第２シーケンスが「今日−私は−香山に−行く−つもりである」であると、被切替単語である「香山」及び「つもり」が、第１シーケンス及び第２シーケンスにすべて存在するため、指定された集合中に記録するデータは、「香山に−Ｓ１３、つもりである−Ｓ１５、香山−Ｓ２３、つもりである−Ｓ２５」である。
【００６１】
本発明の実施例において、「香山に」及び「つもり」を、第１文字列及び第２文字列との間の一つのペアリングの単語として定義する。上記の例から分かるように、ペアリングの単語とは、第１シーケンス及び第２シーケンス中に同時に存在する任意の二つの単語である。
【００６２】
ステップＳ２０５２において、切替操作情報に基づいて、ペアリングの数を特定する。
【００６３】
ここで、ペアリングの数とは、第１シーケンス及び第２シーケンス中のペアリングの単語の数であり、即ち、第１シーケンス及び第２シーケンスの両方の中に同時に存在する二つの単語の数である。上記の指定された集合中に記録するデータに対する説明から分かるように、指定された集合中に記録するデータに基づいて、ペアリングの数を特定する。
【００６４】
例えば、指定された集合中に記録するデータが「香山に−Ｓ１３、つもりである−Ｓ１５、香山−Ｓ２３、つもりである−Ｓ２５、私は−Ｓ１１、行く−Ｓ１４、私は−Ｓ２２、行く−Ｓ２４」であると、ペアリングの数を２として特定する。
【００６５】
ステップＳ２０５３において、編集距離、ペアリングの数、各操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の類似性を特定する。
【００６６】
一例として、本発明の実施例において、編集距離、ペアリングの数、各操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の類似性を特定する時に、各操作は、切替操作、及び交換操作を含む。
【００６７】
各操作の種類に組み合わせると、ステップＳ２０５３は、以下のステップＳ２０５３１乃至ステップＳ２０５３３によって実現される。
【００６８】
ステップＳ２０５３１において、単語編集距離、単語ペアリングの数、切替操作の操作コスト、および、交換操作の操作コストに基づいて、第１文字列と第２文字列との間の最小のセマンティックの編集距離を特定する。
【００６９】
一例として、編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、以下の式２に従って、第１文字列と第２文字列との間の最小のセマンティックの編集距離を特定する。
式２：minCost(S1, S2)=d-p(2cost(T)-cost(J))
式２の中で、S1及びS2は、それぞれ第１文字列及び第２文字列であり、minCost(S1, S2)は、最小のセマンティックの編集距離であり、ｄは、編集距離であり、ｐは、ペアリングの数であり、cost(J)は、交換操作の操作コストであり、cost(T)は、切替操作の操作コストであり、且つ、2cost(T)-cost(J)>0である。
【００７０】
ステップＳ２０５３２において、最小のセマンティックの編集距離を正規化して、正規化結果を得る。
【００７１】
一例として、第１文字列と第２文字列との間の最大セマンティックの編集距離に基づいて、最小のセマンティックの編集距離を正規化する。最大セマンティックの編集距離は、以下の式４のとおりである。
式４：normFact(S1, S2)=min(n, m)cost(T)+(max(n, m)-min(n, m))×costM
costM=cost(C),  if n<m
costM=cost(S),  if n>m
式４の中で、normFact(S1, S2)は、第２セマンティックの編集距離であり、ｎは、第１シーケンスの単語の数であり、ｍは、第２シーケンスの単語の数である。
【００７２】
最小のセマンティックの編集距離minCost(S1, S2)に対して、正規化処理して得た正規化結果は、minCost(S1, S2)/normFact(S1, S2)である。最小のセマンティックの編集距離を正規化して、minCost(S1, S2)/normFact(S1, S2)を、０から１の間にマッピングして、類似性をもっと直観的に特定できる。
【００７３】
ステップＳ２０５３３において、単語正規化結果に基づいて、第１文字列と第２文字列との間の類似性を特定する。
【００７４】
一例として、単語正規化結果に基づいて、以下の式５に従って、第１文字列と第２文字列との間の類似性を特定する。
式５：sim(S1, S2)=1-minCost(S1, S2)/normFact(S1, S2)
式５の中で、sim(S1, S2)は、上記第１文字列と上記第２文字列との間の類似性であり、minCost(S1, S2)は、最小のセマンティックの編集距離であり、normFact(S1, S2)は、最大のセマンティックの編集距離であり、minCost(S1, S2)/normFact(S1, S2)は、正規化結果である。
【００７５】
もっと具体的に、本発明の実施例において、編集距離、ペアリングの数、各操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の類似性を特定する時に、各操作は、切替操作、交換操作、挿入操作、削除操作中の少なくとも一つを含む。これを基に、以下のステップＳ２０５３４乃至ステップＳ２０５３６によって実現できる。
【００７６】
ステップＳ２０５３４において、編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、第１文字列と第２文字列との間の第１セマンティックの編集距離を特定する。
【００７７】
ここで、第１セマンティックの編集距離は、第１文字列と第２文字列との間の最小のセマンティックの編集距離である。
【００７８】
一例として、編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、第１文字列と第２文字列との間の第１セマンティックの編集距離を特定する時に、以下の式３に従って実現できるが、これに限定されない。
式３：minCost(S1, S2)=d-p(2cost(T)-cost(J))
式３の中で、S1及びS2は、それぞれ上記第１文字列及び上記第２文字列であり、minCost(S1, S2)は、上記第１セマンティックの編集距離であり、ｄは、上記編集距離であり、ｐは、上記ペアリングの数であり、cost(J)は、上記交換操作の操作コストである。
【００７９】
式３及び式２から分かるように、第１セマンティックの編集距離は、第１文字列と第２文字列との間の最小のセマンティックの編集距離である。式２と式３は、minCost(S1, S2)の意味のみ互いに異なる。
【００８０】
ステップＳ２０５３５において、挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の第２セマンティックの編集距離を特定する。
【００８１】
ここで、第２セマンティックの編集距離は、第１文字列と第２文字列との間の最大セマンティックの編集距離である。
【００８２】
一例として、挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の第２セマンティックの編集距離を特定する時に、以下の式４に従って実現できるが、これに限定されない。
式４：normFact(S1, S2)=min(n, m)cost(T)+(max(n, m)-min(n, m))×costM
costM=cost(C),  if n<m
costM=cost(S),  if n>m
式４の中で、normFact(S1, S2)は、上記第２セマンティックの編集距離であり、ｎは、上記第１シーケンスの単語の数であり、ｍは、上記第２シーケンスの単語の数である。
ここで、normFact(S1, S2)は、正規化係数であり、minCost(S1, S2)/normFact(S1, S2)を、０から１の間にマッピングして、類似性を直観的に特定できる。
【００８３】
ステップＳ２０５３６において、第１セマンティックの編集距離、及び、第２セマンティックの編集距離に基づいて、第１文字列と第２文字列との間の類似性を特定する。
【００８４】
一例として、以下の式５に従って、第１文字列と第２文字列との間の類似性を特定する。
式５：sim(S1, S2)=1-minCost(S1, S2)/normFact(S1, S2)
式５の中で、sim(S1, S2)は、上記第１文字列と上記第２文字列との間の類似性である。
【００８５】
例えば、minCost(S1, S2)が１.５であり、normFact(S1, S2)が２.５であると、Ｓ１とＳ２との間の類似性は、１−１.５/２.５＝０.４である。
【００８６】
本発明の実施例によって提供する方法によると、第１文字列及び第２文字列を、それぞれ、第１シーケンス及び第２シーケンスに単語分割して、第１文字列から第２文字列に変換する時の編集距離を特定する時に、第１文字列及び第２文字列の中の各文字に基づいて実現するのではなく、第１シーケンス及び第２シーケンスの中の各単語に基づいて実現する。ここで、文字列の中の各単語は少なくとも一つの文字を含む可能があるため、編集距離に基づいて類似性を特定する時に、文字列の中の各文字同士との間の関連関係を組み合わせたので、特定した類似性がもっと正確になる。
【００８７】
図３は、例示的な一実施例に係る類似性特定装置を示すブロック図である。図３を参照すると、当該類似性特定装置は、単語分割モジュール３０１、第１特定モジュール３０２及び第２特定モジュール３０３を備える。
【００８８】
単語分割モジュール３０１は、第１文字列及び第２文字列に対してそれぞれ単語分割を行なって、少なくとも一つの単語がそれぞれ含まれた第１シーケンス及び第２シーケンスを得る。
【００８９】
第１特定モジュール３０２は、予め定義した編集距離アルゴリズム、第１シーケンス、及び第２シーケンスに基づいて、第１文字列及び第２文字列との間の編集距離を特定する。
【００９０】
第２特定モジュール３０３は、編集距離、及び、第１シーケンスから第２シーケンスに変換するために行う各操作の情報に基づいて、第１文字列と第２文字列との間の類似性を特定する。
【００９１】
本発明の実施例によって提供する装置によると、第１文字列及び第２文字列を、第１シーケンス及び第２シーケンスに単語分割することにより、編集距離を特定する時に、文字列の中の文字に基づいて実現するのではなく、文字列の中の単語に基づいて実現する。ここで、文字列の中の各単語は少なくとも一つの文字を含む可能があるため、編集距離に基づいて類似性を特定する時に、文字列の中の各文字同士との間の関連関係を組み合わせたので、特定した類似性がもっと正確になる。
【００９２】
もう一実施例において、図４を参照すると、第２特定モジュール３０３は、
第１シーケンスから第２シーケンスに変換するために行う各操作情報の中の切替操作情報を取得するための取得ユニット３０３１と、
各切替操作情報に基づいて、第１シーケンス及び第２シーケンスの両方の中に同時に存在する二つの単語の数である、ペアリングの数を特定するための第１特定ユニット３０３２と、
編集距離、ペアリングの数、各操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の類似性を特定するための第２特定ユニット３０３３と
を備える。
【００９３】
もう一実施例において、図５を参照すると、各操作包括は、切替操作、及び、交換操作を含み、第２特定ユニット３０３３は、
編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、第１文字列と第２文字列との間の最小のセマンティックの編集距離を特定するための第１特定サブユニット３０３３１と、
最小のセマンティックの編集距離を正規化して、正規化結果を得るための正規化サブユニット３０３３２と、
正規化結果に基づいて、第１文字列と第２文字列との間の類似性を特定するための第２特定サブユニット３０３３３と
を備える。
【００９４】
もう一実施例において、図６を参照すると、各操作は、切替操作、及び、交換操作、挿入操作、及び、削除操作の中の少なくとも一つを含み、第２特定ユニット３０３３は、
編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、第１文字列と第２文字列との間の第１セマンティックの編集距離を特定するための第３特定サブユニット３０３３４と、
挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、第１文字列と第２文字列との間の第２セマンティックの編集距離を特定するための第４特定サブユニット３０３３５と、
第１セマンティックの編集距離、及び、第２セマンティックの編集距離に基づいて、第１文字列と第２文字列との間の類似性を特定するための第５特定サブユニット３０３３６と
を備える。
【００９５】
もう一実施例において、図７を参照すると、装置は、
切替操作と交換操作との間の関係に基づいて、切替操作の操作コスト及び交換操作の操作コストを特定するための第３特定モジュール３０４と、
切替操作、挿入操作、及び、削除操作の間の関係に基づいて、挿入操作の操作コスト、削除操作の操作コスト及び切替操作の操作コストを特定するための第４特定モジュール３０５と
をさらに備える。
【００９６】
もう一実施例において、図８を参照すると、装置は、
切替操作と交換操作との間の関係に基づいて、２×切替操作の操作コスト＞交換操作の操作コストとして特定するための第５特定モジュール３０６と、
切替操作、挿入操作、及び、削除操作の間の関係に基づいて、挿入操作の操作コスト+削除操作の操作コスト＞切替操作の操作コストとして特定するための第６特定モジュール３０７と
をさらに備える。
【００９７】
もう一実施例において、図９を参照すると、装置は、
挿入操作と削除操作との間の関係に基づいて、挿入操作の操作コスト＝削除操作の操作コストとして特定するための第７特定モジュール３０８をさらに備える。
【００９８】
もう一実施例において、第１特定モジュール３０２は、予め定義した編集距離アルゴリズム、第１シーケンス、及び第２シーケンスに基づいて、以下の式１に従って、第１文字列及び第２文字列との間の編集距離を特定する。
式１：minCost[i, j]=min(
minCost[i-1, j]+cost(S),
minCost[i, j-1]+cost(C),
minCost[i-1, j-1]+cost(T))
式１の中で、ｉは、第１シーケンス中のｉ番目の単語であり、ｊは、第２シーケンス中のｊ番目の単語であり、cost(S)は、削除操作の操作コストであり、cost(C)は、挿入操作の操作コストであり、cost(T)は、切替操作の操作コストである。
【００９９】
もう一実施例において、第１特定サブユニット３０３３１は、編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、以下の式２に従って、第１文字列と第２文字列との間の最小のセマンティックの編集距離を特定する。
式２：minCost(S1, S2)=d-p(2cost(T)-cost(J))
式２の中で、S1及びS2は、それぞれ第１文字列及び第２文字列であり、minCost(S1, S2)は、最小のセマンティックの編集距離であり、ｄは、編集距離であり、ｐは、ペアリングの数であり、cost(J)は、交換操作の操作コストであり、cost(T)は、切替操作の操作コストであり、且つ、2cost(T)-cost(J)>0である。
【０１００】
もう一実施例において、第３特定サブユニット３０３３４は、編集距離、ペアリングの数、切替操作の操作コスト、及び、交換操作の操作コストに基づいて、以下の式３に従って、第１文字列と第２文字列との間の第１セマンティックの編集距離を特定する。
式３：minCost(S1, S2)=d-p(2cost(T)-cost(J))
式３の中で、S1及びS2は、それぞれ第１文字列及び第２文字列であり、minCost(S1, S2)は、第１セマンティックの編集距離であり、ｄは、編集距離であり、ｐは、ペアリングの数であり、cost(J)は、交換操作の操作コストであり、cost(T)は、切替操作の操作コストであり、且つ、2cost(T)-cost(J)>0である。
【０１０１】
もう一実施例において、第４特定サブユニット３０３３５は、挿入操作の操作コスト及び削除操作の操作コストの中の一つ、切替操作の操作コスト、第１シーケンス中の単語の数、及び、第２シーケンス中の単語の数に基づいて、以下の式４に従って、第１文字列と第２文字列との間の第２セマンティックの編集距離を特定する。
式４：normFact(S1, S2)=min(n, m)cost(T)+(max(n, m)-min(n, m))×costM
costM=cost(C),  if n<m
costM=cost(S),  if n>m
式４の中で、normFact(S1, S2)は、第２セマンティックの編集距離であり、ｎは、第１シーケンスの単語の数であり、ｍは、第２シーケンスの単語の数であり、cost(T)は、切替操作の操作コストであり、cost(S)は、削除操作の操作コストであり、cost(C)は、挿入操作の操作コストである。
【０１０２】
もう一実施例において、第５特定サブユニット３０３３６は、第１セマンティックの編集距離、及び、第２セマンティックの編集距離に基づいて、以下の式５に従って、第１文字列と第２文字列との間の類似性を特定する。
式５：sim(S1, S2)=1-minCost(S1, S2)/normFact(S1, S2)
式５の中で、sim(S1, S2)は、第１文字列と第２文字列との間の類似性であり、minCost(S1, S2)は、第１セマンティックの編集距離であり、normFact(S1, S2)は、第２セマンティックの編集距離である。
【０１０３】
上記の全てのオプション的な構成を、任意の組合せによって、本発明のオプション的な実施例を実現することができ、ここでは繰り返して説明しない。
【０１０４】
上記の図３乃至図９に対応される実施例によって提供する類似性特定装置は、上記の図１或いは図２に対応される実施例によって提供する類似性特定方法を実行できる。その中の各モジュールが実行する操作の具体的な形態は既に当該方法に関する実施例において詳細に説明したため、ここでは詳細に説明しない。
【０１０５】
図１０は、例示的な一実施例に係る端末６００を示すブロック図である、上記端末は、上記の図１或いは図２に対応する実施例によって提供する類似性特定方法を実行する。例えば、端末６００は、携帯電話、コンピューター、デジタル放送端末、メッセージ送受信デバイス、ゲームコンソール、タブレットデバイス、医療機器、フィットネス機器、パーソナルデジタルアシスタント等であってもよい。
【０１０６】
図１０を参照して、端末６００は、プロセスアセンブリ６０２、メモリ６０４、電源アセンブリ６０６、マルチメディアアセンブリ６０８、オーディオアセンブリ６１０、入出力（Ｉ／Ｏ）インターフェイス６１２、センサアセンブリ６１４、及び通信アセンブリ６１６のような一つ以上のアセンブリを含んでよい。
【０１０７】
プロセスアセンブリ６０２は、一般的には端末６００の全体の動作を制御するものであり、例えば、表示、電話呼び出し、データ通信、カメラ動作、及び記録動作と関連する動作を制御する。プロセスアセンブリ６０２は、一つ以上のプロセッサ６２０を含み、これらによって命令を実行することにより、上記の方法の全部、或は一部のステップを実現するようにしてもよい。なお、プロセスアセンブリ６０２は、一つ以上のモジュールを含み、これらによってプロセスアセンブリ６０２と他のアセンブリの間のインタラクションを容易にするようにしてもよい。例えば、プロセスアセンブリ６０２は、マルチメディアモジュールを含み、これらによってマルチメディアアセンブリ６０８とプロセスアセンブリ６０２の間のインタラクションを容易にするようにしてもよい。
【０１０８】
メモリ６０４は、各種類のデータを記憶することにより端末６００の動作を支援するように構成される。これらのデータの例は、端末６００において動作するいずれのアプリケーションプログラム又は方法の命令、連絡対象データ、電話帳データ、メッセージ、画像、ビデオ等を含む。メモリ６０４は、いずれの種類の揮発性メモリ、不揮発性メモリ記憶デバイスまたはそれらの組み合わせによって実現されてもよく、例えば、ＳＲＡＭ（ＳｔａｔｉｃＲａｎｄｏｍＡｃｃｅｓｓＭｅｍｏｒｙ）ＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ Ｅｒａｓａｂｌｅ Ｐｒｏｇｒａｍｍａｂｌｅ Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＥＰＲＯＭ（Ｅｒａｓａｂｌｅ Ｐｒｏｇｒａｍｍａｂｌｅ Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＰＲＯＭ（ Ｐｒｏｇｒａｍｍａｂｌｅ ＲＯＭ）、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｂｅｒ）、磁気メモリ、フラッシュメモリ、磁気ディスク、或いは光ディスクである。
【０１０９】
電源アセンブリ６０６は、端末６００の多様なアセンブリに電力を供給する。電源アセンブリ６０６は、電源管理システム、一つ以上の電源、及び端末６００のための電力の生成、管理及び割り当てに関連付けられている他のアセンブリを含んでもよい。
【０１１０】
マルチメディアアセンブリ６０８は、前記端末６００とユーザの間に一つの出力インターフェイスを提供するスクリーンを含む。上記の実施例において、スクリーンは液晶モニター（ＬＣＤ）とタッチパネル（ＴＰ）を含んでもよい。スクリーンがタッチパネルを含むことにより、スクリーンはタッチスクリーンを実現することができ、ユーザからの入力信号を受信することができる。タッチパネルは一つ以上のタッチセンサを含んでおり、タッチ、スワイプ、及びタッチパネル上のジェスチャを検出することができる。前記タッチセンサは、タッチ、或はスワイプの動作の境界だけでなく、前記のタッチ、或はスワイプ操作に係る継続時間及び圧力も検出できる。上記の実施例において、マルチメディアアセンブリ６０８は、一つのフロントカメラ、及び／又はリアカメラを含む。端末６００が、例えば撮影モード、或はビデオモード等の動作モードにある場合、フロントカメラ、及び／又はリアカメラは外部からマルチメディアデータを受信できる。フロントカメラとリアカメラのそれぞれは、一つの固定型の光レンズ系、或は可変焦点距離と光学ズーム機能を有するものであってもよい。
【０１１１】
オーディオアセンブリ６１０は、オーディオ信号を入出力するように構成されてもよい。例えば、オーディオアセンブリ６１０は、一つのマイク（ＭＩＣ）を含み、端末６００が、例えば呼出しモード、記録モード、及び音声認識モード等の動作モードにある場合、マイクは外部のオーディオ信号を受信することができる。受信されたオーディオ信号は、さらにメモリ６０４に記憶されたり、通信アセンブリ６１６を介して送信されたりされる。上記の実施例において、オーディオアセンブリ６１０は、オーディオ信号を出力するための一つのスピーカーをさらに含む。
【０１１２】
Ｉ／Ｏインターフェイス６１２は、プロセスアセンブリ６０２と周辺インターフェイスモジュールの間にインターフェイスを提供するものであり、上記周辺インターフェイスモジュールは、キーボード、クリックホイール、ボタン等であってもよい。これらのボタンは、ホームボタン、ボリュームボタン、作動ボタン、ロッキングボタンを含んでもよいが、これらに限定されない。
【０１１３】
センサアセンブリ６１４は、端末６００に各種の状態に対する評価を提供するための一つ以上のセンサを含む。例えば、センサアセンブリ６１４は、端末６００のＯＮ／ＯＦＦ状態、端末６００のディスプレイとキーパッドのようなアセンブリの相対的な位置決めを検出できる。また、例えば、センサアセンブリ６１４は、端末６００、或は端末６００の一つのアセンブリの位置変更、ユーザと端末６００とが接触しているか否か、端末６００の方位、又は加速／減速、端末６００の温度の変化を検出できる。センサアセンブリ６１４は、何れの物理的接触がない状態にて付近の物体の存在を検出するための近接センサを含んでもよい。センサアセンブリ６１４は、撮影アプリケーションに適用するため、ＣＭＯＳ、又はＣＣＤ画像センサのような光センサを含んでもよい。上記の実施例において、当該センサアセンブリ６１４は、加速度センサ、ジャイロスコープセンサ、磁気センサ、圧力センサ、及び温度センサをさらに含んでもよい。
【０１１４】
通信アセンブリ６１６は、端末６００と他の機器の間に有線、又は利便性のよい形態の通信を提供する。端末６００は、例えばＷｉＦｉ（登録商標）、２Ｇ、３Ｇ、或はこれらの組み合わせのような、通信規格に基づいた無線ネットワークに接続されてもよい。一つの例示的な実施例において、通信アセンブリ６１６は、放送チャンネルを介して外部の放送管理システムからの放送信号、又は放送に関連する情報を受信する。一つの例示的な実施例において、前記通信アセンブリ６１６は、近距離無線通信（ＮＦＣ）モジュールをさらに含むことにより、近距離通信を可能にする。例えば、ＮＦＣモジュールは、ＲＦＩＤ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）技術、ＩｒＤＡ（Ｉｎｆｒａｒｅｄ Ｄａｔａ Ａｓｓｏｃｉａｔｉｏｎ）技術、ＵＷＢ（Ｕｌｔｒａ Ｗｉｄｅ Ｂａｎｄ）技術、ＢＴ（Ｂｌｕｅｔｏｏｔｈ（登録商標））技術、他の技術に基づいて実現できる。
【０１１５】
例示的な実施例において、端末６００は、一つ以上のＡＳＩＣ（ＡｐｐｌｉｃａｔｉｏｎＳｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｏｒ）、ＤＳＰＤ（Ｄｉｇｉｔａｌ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｄｅｖｉｃｅ）、ＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）、コントローラ、マイクロコントローラ、マイクロプロセッサ、または他の電子部品によって実現されるものであり、上記方法を実行する。
【０１１６】
例示的な実施例において、さらに、命令を含むコンピュータ読取り可能な非一時的な記録媒体、例えば命令を含むメモリ６０４を提供しており、端末６００のプロセッサ６２０により上記命令を実行して上記方法を実現する。例えば、前記コンピュータ読取り可能な非一時的な記録媒体は、ＲＯＭ、ＲＡＭ、ＣＤ-ＲＯＭ、磁気テープ、フロッピーディスク（登録商標）、光データ記憶デバイス等である。
【０１１７】
本発明の実施例によって提供するコンピュータ読取り可能な非一時的な記録媒体は、第１文字列及び第２文字列を、それぞれ、第１シーケンス及び第２シーケンスに単語分割して、第１文字列から第２文字列に変換する時の編集距離を特定する時に、第１文字列及び第２文字列の中の各文字に基づいて実現するのではなく、第１シーケンス及び第２シーケンスの中の各単語に基づいて実現する。ここで、文字列の中の各単語は少なくとも一つの文字を含む可能があるため、編集距離に基づいて類似性を特定する時に、文字列の中の各文字同士との間の関連関係を組み合わせたので、特定した類似性がもっと正確になる。
【０１１８】
当然ながら、上記の図１或いは図２に対応する実施例によって提供する類似性特定方法は、サーバによっても実行できる。図１１は、例示的な一実施例に係るサーバを示すブロック図である。当該サーバは、上記の図１或いは図２に対応する実施例によって提供する類似性特定方法を実行できる。図１１を参照すると、サーバ７００は、プロセスアセンブリ７２２を備える。当該プロセスアセンブリ７２２は、一つ以上のプロセッサ、及びメモリ７３２を代表とするメモリリソースを、さらに備える。当該メモリリソースは、プロセスアセンブリ７２２によって実行される、例えばアプリケーションプログラムのような命令を保存する。メモリ７３２中に保存されたアプリケーションプログラムには、それぞれ一つの命令のセットに対応する一つ以上のモジュールを含まれてもよい。なお、プロセスアセンブリ７２２は、命令を実行することにより、上記の図１或いは図２に対応する実施例によって提供する類似性特定方法を実行する。
【０１１９】
サーバ７００は、サーバ７００の電源を管理するための一つの電源アセンブリ７２６、サーバ７００をネットワークに接続させるための一つの有線又は無線のネットワークインターフェイス７５０、及び、一つの入出力インターフェイス７５８を備えてもよい。サーバ７００は、メモリ７３２に保存された、例えば、Ｗｉｎｄｏｗｓ  ＳｅｒｖｅｒＴＭ、Ｍａｃ  ＯＳ  ＸＴＭ、ＵｎｉｘＴＭ，  ＬｉｎｕｘＴＭ、ＦｒｅｅＢＳＤＴＭのようなオペレーティング・システムによって、操作を行うことができる。
【０１２０】
当業者は、明細書を検討して本発明を実施した後、本発明の他の実施例を容易に考え出すことができる。本願は、本発明のいずれの変形、用途、又は適応的な変更をカバーすることを意図しており、これらの変形、用途、又は適応的な変更は、本発明の一般的な原理に従い、また、本発明は公開していない当該技術分野の公知の知識又は通常の技術手段を含む。明細書と実施例はただ例示として考慮され、本発明の本当の範囲と趣旨は以下の特許請求の範囲に記載される。
【０１２１】
本発明は上記に記述され、また図面で示した厳密な構成に限定されず、その範囲を逸脱しない限り多様な置換えと変更を行うことができると、理解されるべきである。本発明の範囲は添付の特許請求の範囲のみにより限定される。
【図１】
0006321306.tif 000002
【図２】
0006321306.tif 000003
【図３】
0006321306.tif 000004
【図４】
0006321306.tif 000005
【図５】
0006321306.tif 000006
【図６】
0006321306.tif 000007
【図７】
0006321306.tif 000008
【図８】
0006321306.tif 000009
【図９】
0006321306.tif 000010
【図１０】
0006321306.tif 000011
【図１１】
0006321306.tif 000012