Speeding Up String Pattern Matching by Text Compression: The Dawn of a New Era (特集 〔情報処理学会〕創立40周年記念論文)
スポンサーリンク
概要
- 論文の詳細を見る
This paper describes our recent studies on string pattern matching in compressed texts mainly from practical viewpoints. The aim is to speed up the string pattern matching task, in comparison with an ordinary search over the original texts. We have successfully developed(1)an Ac type algorithm forsearching in Huffman encoded files, and(2)a KMP type algorithm and(3)a BM type algorithm for searching in files compressed by the so-called byte pair encoding(BPE). Each of the algorithms reduces the search time at nearly the same rate as the compression ratio. Surprisingly, the BM type algorithm runs over BPE compressed files about 1.2-3.0 times faster than the exact match routines of the software package agrep, which is known as the fastest pattern matching tool.
- 2001-03-15
著者
-
ARIKAWA SETSUO
Department of Informatics, Kyushu University
-
Matsumoto Tetsuya
Department of Cardiovascular and Respiratory Medicine, Shiga University of Medical Science
-
Arikawa S
Kyushu Univ.
-
Arikawa Setsuo
Department Of Informatics Kyushu University
-
TAKEDA Masayuki
Department of Urology, Niigata University School of Medicine
-
Shibata Yusuke
Department of Pharmaceutics and Biopharmaceutics, Showa Pharmaceutical University
-
KIDA TAKUYA
Department of Informatics, Kyushu University
-
SHINOHARA AYUMI
Department of Informatics, Kyushu University
-
FUKAMACHI SHUICHI
Department of Artificial Intelligence, Kyushu Institute of Technology
-
SHINOHARA TAKESHI
Department of Artificial Intelligence, Kyushu Institute of Technology
-
Arikawa Setsuo
Dept.of Informatics Grad.school Of Information Sci.and Electrical Eng. Kyushu Univ.
-
Matsumoto Tetsuya
Department Of Cardiovascular And Respiratory Medicine Shiga University Of Medical Science
-
Kida Takuya
Department Of Informatics Kyushu University
-
Shibata Yusuke
Department Of Informatics Kyushu University:present Address Ntt Comware
-
Takeda Masayuki
Department Of Urology Niigata University School Of Medicine
-
Shinohara Ayumi
Department Of Informatics Kyushu University
-
Shinohara Takeshi
Department Of Artificial Intelligence Kyushu Institute Of Technology
-
Fukamachi Shuichi
Department Of Artificial Intelligence Kyushu Institute Of Technology
-
Matsumoto Tetsuya
Department Of Cardiovascular And Respiratory Medicine
-
Takeda Masayuki
Department Of Informatics Kyushu University
-
Matsumoto Tetsuya
Department Of Informatics Kyushu University
-
Takeda Masayuki
Department Of Computer Science Tokyo Institute Of Technology
-
Takeda Masayuki
Department Of Biochemistry And Engineering Faculty Of Engineering Tohoku University
関連論文
- Speeding Up String Pattern Matching by Text Compression: The Dawn of a New Era (特集 〔情報処理学会〕創立40周年記念論文)
- Refutability and Reliability for Inductive Inference of Recursive Real-Valued Functions
- Whole-Body Periodic Acceleration Enhances Brachial Endothelial Function
- PJ-457 Chronic Effects of Angiotensin II Receptor Blockade on Coronary Fibrinolytic Function in Patients with Coronary Artery Disease(Coronary circulation, basic/clinical-3, The 71st Annual Scientific Meeting of the Japanese Circulation Society)
- PJ-453 Effects of Chronic Smoking on Coronary Fibrinolytic Function in Women with Normal Coronary Arteries(Coronary circulation, basic/clinical-2, The 71st Annual Scientific Meeting of the Japanese Circulation Society)
- Impact of Paraoxonase Polymorphism (Q192R) on Endothelial Function in Intact Coronary Circulation
- PJ-388 The Impact of Whole-body, Periodic Acceleration on Vascular Endothelial Function and Nitric Oxide Release(Exercise test/Cardiac rehabilitation-3 (IHD) PJ66,Poster Session (Japanese),The 70th Anniversary Annual Scientific Meeting of the Japanese Cir
- PJ-010 Aortic Stiffening Precedes Coronary Endothelial Dysfunction in Type II Diabetes Mellitus(Coronary circulation, basic/clinical-4 (IHD) PJ2,Poster Session (Japanese),The 70th Anniversary Annual Scientific Meeting of the Japanese Circulation Society)
- PJ-388 The Impact of Whole-body, Periodic Acceleration on Vascular Endothelial Function and Nitric Oxide Release(Exercise test/Cardiac rehabilitation-3 (IHD) PJ66,Poster Session (Japanese),The 70th Anniversary Annual Scientific Meeting of the Japanese Cir
- Multi-Objective Genetic Programming with Redundancy-Regulations for Automatic Construction of Image Feature Extractors
- Linear GP with Redundancy-removed Recombination for Synthesis of Image Feature Extraction Programs
- Potential Activity of Carrageenan to Enhance Antibacterial Host-Defense Systems in Mice
- Retroperitoneoscopy-assisted renal biopsy for pediatric patients : Comparison withretroperitoneoscopic renal biopsy
- Serum ICAM-1 in Renal Cell Cancer Patients : Possible Significance for Presence of Metastatic Disease
- Laparoscopy-Assisted Two-Stage Fowler-Stephens Orchiopexy for Intra-abdominal Nonpalpable Testis
- Effect of Particle Size of Drug on Conversion of Crystals to an Amorphous State in a Solid Dispersion with Crospovidone
- Counting and Verifying Maximal Palindromes
- Role of Impaired Sympathetic Nerve Function in Enhancing Coronary Vasoconstriction in Patients with Hypertrophic Cardiomyopathy(Cardiomyopathy, Clinical 2 (M), The 69th Annual Scientific Meeting of the Japanese Circulation Society)
- Endothelial Dysfunction May Play a Role in Left Ventricular Remodeling after Primary Coronary Angioplasty for Acute Myocardial Infarction(Acute Myocardial Infarction, Clinical (Pathophysiology) 4 (IHD), The 69th Annual Scientific Meeting of the Japanese C
- OE-094 Noninvasive Evaluation of Coronary Artery Plaque with ECG-Gated Multislice Computed Tomography(X-ray/CT/MRI/DSA 1 (I) : OE11)(Oral Presentation (English))
- Interfering Factors in Helping Quit Smoking in Patients with Ischemic Heart Disease
- ACE I/D Polymorphism Is a Determinant of Coronary Release of Tissue Plasminogen Activator in Response to Bradykinin
- Body Mass Index Is an Independent Determinant of Coronary and Peripheral Endothelial Function
- The Relationship between Aortic Pulse Wave Velocity and Coronary Endothelial Function
- Endogenous Coronary Fibrinolytic Activity Is Reduced in Patients with Type II Diabetes : Effects of Coronary Tissue Plasminogen Activator Release
- Effects of the Paraoxonase Polymorphism (Q192R) on Endothelium-Dependent Coronary Vasomotor Responses
- Linear GP with redundancy-removed recombination for synthesis of image feature extraction programs (数理モデル化と問題解決・バイオ情報学)
- Sepsis Caused by Food-borne Infection with Escherichia coli
- In Vitro and In Vivo Antibacterial Activities of Quinupristin-Dalfopristin, a Novel Injectable Streptogramin, against Gram-Positive Cocci and Gram-Negative Respiratory Tract Pathogens
- Role of Motility in the Endogenous Pseudomonas aeruginosa Sepsis after Burn
- Bacterial Translocation of Intestinal Pseudomonas aeruginosa in Post-Burn Infection of Mice
- OE-158 Novel Anatomical Observations of the Left Atrium and the Pulmonary Vein by Multi-Detector Computed Tomography in Patients with Atrial Fibrillation(CT/DSA-1 (I) OE27,Oral Presentation (English),The 70th Anniversary Annual Scientific Meeting of the J
- Prognostic value of ECG-gated thallium-201 single-photon emission tomography in patients with coronary artery disease
- Relationship between exercise capacity and cardiac diastolic function assessed by time-volume curve from 16-frame gated myocardial perfusion SPECT
- PJ-532 Angiotensin-Converting Enzyme Inhibition Increases Constitutive Release of Tissue Plasminogen Activator in Coronary Circulation(PJ090,Coronary Circulation/Chronic Coronary Disease (Basic/Clinical) (IHD),Poster Session (Japanese),The 73rd Annual Sci
- PJ-445 Clinical Difference of Radial Augmentation Index and Pulse Wave Velocity as Indicators of Cardiovascular Stiffness(PJ075,Hypertension, Clinical 1 (H),Poster Session (Japanese),The 73rd Annual Scientific Meeting of The Japanese Circulation Society)
- Pathological study on sibling autopsy cases of the late infantile form of neuronal ceroid lipofuscinosis
- Prevalence of Chlamydophila pneumoniae among Bangladeshi children under age 5 years with acute respiratory infections
- Evaluation of a rapid antigen detection test for Neisseria gonorrhoeae in urine sediment for diagnosis of gonococcal urethritis in males
- High frequency of erythromycin A resistance and distribution of mefE and ermB genes in clinical isolates of Streptococcus pneumoniae in Japan
- Potential of macrolide antibiotics to inhibit protein synthesis of Pseudomonas aeruginosa : suppression of virulence factors and stress response
- In Vitro and In Vivo Evaluation of DU6859a, A New Fluoroquinolone, among Injectable Antibacterials Tested ageinst Clinical Isolates
- Brachial Artery Flow-Mediated Vasodilation Is Correlated with Coronary Vasomotor and Fibrinolytic Responses Induced by Bradykinin
- Angiotensin-Converting Enzyme Insertion/Deletion Polymorphism Modulates Coronary Release of Tissue Plasminogen Activator in Response to Bradykinin
- Clinical guidelines for overactive bladder
- Acceleration of Genetic Programming by Hierarchical Structure Learning : A Case Study on Image Recognition Program Synthesis
- Clinical significance of diastolic function as an indicator of myocardial ischemia assessed by 16-frame gated myocardial perfusion SPECT
- PE-274 Cardiac Diastolic Function as an Indicator of Myocardial Ischemia Estimated by 16-Frame Gated Myocardial Perfusion SPECT(Cardiac function, basic/clinical(03)(M),Poster Session(English),The 72nd Annual Scientific Meeting of the Japanese Circulation
- Assessment of cardiac function in patients with heart disease by quantitative gated myocardial perfusion SPECT
- PE-362 A Novel Clinical Indicator Using Tc-99m Sestamibi for Evaluating Cardiac Mitochondrial Function in Patients with Cardiomyopathies(Nuclear cardiology-5, The 71st Annual Scientific Meeting of the Japanese Circulation Society)
- PJ-096 Creatine Kinase System and Fatty Acid Metabolism in Human Failing Hearts(Metabolism/Biochemistry/Energetics-3 (M) PJ16,Poster Session (Japanese),The 70th Anniversary Annual Scientific Meeting of the Japanese Circulation Society)
- PE-061 Cardiac Diastolic Dysfunction is Associated with Sympathetic Nerve Functional Abnormalities in Patients with Stable Heart Failure(Cardiac function, basic/clinical-3 (M) PE11,Poster Session (English),The 70th Anniversary Annual Scientific Meeting of
- Impact of endothelial dysfunction on left ventricular remodeling after successful primary coronary angioplasty for acute myocardial infarction : Analysis by quantitative ECG-gated SPECT
- Dilated cardiomyopathy relieved as a result of β-blocker therapy : A case report-key points in assessment of prognosis based on MIBG myocardial scintigraphy and BNP levels
- Validity of the Ultrasonic Aspirator and Argon Beam Coagulator in Laparoscopic Adrenalectomy for Cushing's Syndrome
- Endoscopic Parathyroidectomy for Ectopic Primary Hyperparathyroidism A Minimally Invasive Procedure for Urolithiasis Patient
- Therapeutic Efficacies of Penicillin G, Cefotaxime, and Imipenem/Cilastatin against Penicillin-Resistant Pneumococcal Pneumonia in CBA/J Mice
- PJ-350 Increased Levels of Lipocalin-type Prostaglandin D Synthase is associated with Plaque Instability in Human Coronary Circulation(Coronary circulation, basic/clinical-5 (IHD) PJ59,Poster Session (Japanese),The 70th Anniversary Annual Scientific Meeti
- Relationship between Coronary Vasomotor Function and Serum Lipocalin-type Prostaglandin D Synthase Level in Coronary Vasospastic Angina (Coronary Circulation, Basic/Clinical 4 (IHD), The 69th Annual Scientific Meeting of the Japanese Circulation Society)
- Role of Lipocalin-type Prostaglandin D Synthase in Atherosclerotic Monkey Coronary Arteries : Effect of Estrogen Replacement Therapy(Atherosclerosis, Basic 5 (IHD), The 69th Annual Scientific Meeting of the Japanese Circulation Society)
- PJ-251 The Impact of Lipocalin-type Prostaglandin D Synthase on Coronary Atherosclerosis and Vasospasm(Coronary circulation, basic/clinical(03)(IHD),Poster Session(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circulation Society)
- Criteria for Inductive Inference with Mind Changes and Anomalies of Recursive Real-Valued Functions (Special Issue on Selected Papers from LA Symposium)
- Assessment of Myocardial Creatine Concentration in Dysfunctional Human Heart by Proton Magnetic Resonance Spectroscopy
- A Novel Method for Predicting Disintegration Time in the Mouth of Rapidly Disintegrating Tablet by Compaction Analysis Using TabAll(Communication to the Editor)
- PE-463 Prognostic Value of Post-Stress Left Ventricular Function by ECG-gated Tl Scintigraphy(Cardiac Function, Basic/Clinical 3 (M) : PE79)(Poster Session (English))
- PE-035 Prognostic Value of Iodine-123 Metaiodobenzylguanidine Imaging in Patients with Heart Failure(Nuclear Cardiology 4 (I) : PE6)(Poster Session (English))
- Lawn Weeds Detection Methods Using Image Processing Techniques
- PE-155 Relationship between Exercise Capacity and Left Ventricular Diastolic Function by Time-volume Curve Analysis(PE026,Cardiac Function (Clinical) 1 (M),Poster Session (English),The 73rd Annual Scientific Meeting of The Japanese Circulation Society)
- PJ-442 Gender Differences in Coronary Microvasomotor Function in Patients with Coronary Vasospastic Angina(Coronary circulation, basic/clinical(04)(IHD),Poster Session(Japanese),The 72nd Annual Scientific Meeting of the Japanese Circulation Society)
- PJ-469 Relationship between Aortic Stiffness and Muscarinic and Bradykinin Receptor-Operated Coronary Vasomotor Responses(Coronary Circulation, Basic/Clinical 4 (IHD) : PJ78)(Poster Session (Japanese))
- PJ-467 Effects of Pravastatin on Endothelium-dependent Coronary Vasomotor and Fibrinolytic Function(Coronary Circulation, Basic/Clinical 4 (IHD) : PJ78)(Poster Session (Japanese))
- OJ-322 Effects of Diabetes on Coronary and Forearm Endothelial Function and Aortic Stiffness(Cardiovascular Pharmacology, Basic/Clinical 2 (H) : OJ39)(Oral Presentation (Japanese))
- Effects of Hypertension on Brachial Artery Flow-Mediated Dilation and Coronary Vasomotor Responses to Bradykinin and Acetylcholine
- A Case of Asymptomatic Submucosal-Type Leiomyoma of the Urinary Bladder Correctly Diagnosed with Magnetic Resonance Imaging (MRI) and Successfully Treated by Transurethral Resection
- Absence of RET Proto-Oncogene Mutations in a Father and Son with Pheochromocytoma and Pancreatic Islet Cell Tumor
- Pure laparoscopic partial nephrectomy for primary renal carcinoid
- Decreased expression of G protein-coupled receptor kinases in the detrusor smooth muscle of human urinary bladder with outlet obstruction
- Modified endoscopic live donor nephrectomy : Retroperitoneoscopy followed by hand-assistance
- Contributions of mucosal immune cells to methotrexate-induced mucositis
- Involvement of Membrane PIP_2 in the Regulation of the Muscarinic K^+ Channel by Extracellular ATP
- Relationship between Coronary Endothelial Function and Aortic Stiffness in Hypertensive Patients : Effects of Adequate Blood Pressure Control (Coronary Circulation, Basic/Clinical 4 (IHD), The 69th Annual Scientific Meeting of the Japanese Circulation Soc
- Clinical guidelines for nocturia
- An Efficient Prover for Elementary Formal Systems
- Knowledge Acquisition from Amino Sequences by Machine Learning System BONSAI
- Efficient Substructure Discovery from Large Semi-Structured Data(Data Mining)
- Treatment of Multiple Intracranial Aneurysms in the Anterior Circulation : Case Report
- Characterization of the Mouse α1D-Adrenergic Receptor Gene
- Laparoscopic Renal Biopsy via the Retroperitoneal Approach : A Case Report
- The Forefront for Novel Therapeutic Agents Based on the Pathophysiology of Lower Urinary Tract Dysfunction: Pathophysiology of Voiding Dysfunction and Pharmacological Therapy
- Simultaneous management for retrocaval ureter and ipsilateral renal stone using retroperitoneoscopic approach: report of a case
- Roles of mechanosensitive ion channels in bladder sensory transduction and overactive bladder
- The use of absorbable clips for renal parenchymal suturing makes warm ischemia time short during laparoscopic partial nephrectomy in a porcine model
- Real-time quantitative analysis for human telomerase reverse transcriptase mRNA and human telomerase RNA component mRNA expressions as markers for clinicopathologic parameters in urinary bladder cancer
- Markov String Grammar
- Current and future directions in diagnostic markers in interstitial cystitis
- Interleukin-1 deficiency in combination with macrophage depletion increases susceptibility to Pseudomonas aeruginosa bacteremia
- Multi-Objective Genetic Programming with Redundancy-Regulations for Automatic Construction of Image Feature Extractors
- Lipocalin-Type Prostaglandin D Synthase Is Associated With Coronary Vasospasm and Vasomotor Reactivity in Response to Acetylcholine
- Refutability and Reliability for Inductive Inference of Recursive Real-Valued Functions
- Refutability and Reliability for Inductive Inference of Recursive Real-Valued Functions