論文

基本情報

氏名 中藤 哲也
氏名(カナ) ナカトウ テツヤ
氏名(英語) NAKATOU TETSUYA
所属 中村学園大学 栄養科学部 栄養科学科
職名 准教授

題名

FFTを用いた近似文字列照合のスコア計算のための最適な写像

単著・共著の別

著者

中藤 哲也
馬場 謙介
森 雅生

担当区分

概要

String matching is the problem of finding all occurrences of a given pattern string in a given text string. It is applicable to a wide range of fields, such as Web information retrieval and pattern discovery of DNA sequences. An extension of the string matching is string matching with mismatches, which allows inexact match with substitution, is expected to have wider application even though it has higher complexity. Several randomized algorithms have been proposed which use fast Fourier transformation (FFT) and run fast to solve the problem. All of these algorithms introduce certain number of mappings that convert symbols into numbers. The total number of such mappings and variance of estimates depends on the method to generate the mappings. The present paper shows an algorithm which achieves the theoretical minimum number of mappings, and yields an estimate with small variance.文字列中から与えられたパターンを見つけ出す文字列照合問題は,Web の情報検索やDNA 配列の特定パターンの検索に用いられるなど,幅広い応用範囲を持つ.パターンの編集に置換のみを許した近似文字列照合は,不一致を許す文字列照合と呼ばれ,単なる文字列照合より応用範囲が広く,また難易度も高い.この問題の解法として,高速フーリエ変換(FFT) を利用した高速な確率アルゴリズムが幾つか提案されている.それらは文字から数値への写像の生成方法により,写像総数と,解の推定値の分散が異なる.本稿で提案するアルゴリズムは,総写像数が理論上での最小であり,推定値の分散も小さい.

発表雑誌等の名称

日本データベース学会letters

出版者

日本データベース学会

6

3

開始ページ

25

終了ページ

28

発行又は発表の年月

2007/12

査読の有無

無し

招待の有無

無し

記述言語

日本語

掲載種別

国際・国内誌

国際共著

ISSN

13478915

eISSN

DOI

Cinii Articles ID

40015793309

Cinii Books ID

Pubmed ID

PubMed Central 記事ID

形式

無償ダウンロード

JGlobalID

arXiv ID

ORCIDのPut Code

DBLP ID