[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

Kociumaka et al., 2018 - Google Patents

Faster recovery of approximate periods over edit distance

Kociumaka et al., 2018

View PDF
Document ID
6782152619481699627
Author
Kociumaka T
Radoszewski J
Rytter W
Straszyński J
Waleń T
Zuba W
Publication year
Publication venue
International Symposium on String Processing and Information Retrieval

External Links

Snippet

The approximate period recovery problem asks to compute all approximate word-periods of a given word S of length n: all primitive words P (| P|= p) which have a periodic extension at edit distance smaller than τ _p from S, where τ _p= ⌊ n (3.75+ ϵ) ⋅ p ⌋ for some ϵ> 0. Here …
Continue reading at arxiv.org (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/21—Text processing
    • G06F17/22—Manipulating or registering by use of codes, e.g. in sequence of text characters
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30964—Querying
    • G06F17/30979—Query processing
    • G06F17/30985—Query processing by using string matching techniques
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/21—Text processing
    • G06F17/24—Editing, e.g. insert/delete
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/27—Automatic analysis, e.g. parsing
    • G06F17/2765—Recognition
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30861—Retrieval from the Internet, e.g. browsers
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/01—Input arrangements or combined input and output arrangements for interaction between user and computer
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F19/00—Digital computing or data processing equipment or methods, specially adapted for specific applications
    • G06F19/10—Bioinformatics, i.e. methods or systems for genetic or protein-related data processing in computational molecular biology
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06N—COMPUTER SYSTEMS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N99/00—Subject matter not provided for in other groups of this subclass
    • G06N99/005—Learning machines, i.e. computer in which a programme is changed according to experience gained by the machine itself during a complete run
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06K—RECOGNITION OF DATA; PRESENTATION OF DATA; RECORD CARRIERS; HANDLING RECORD CARRIERS

Similar Documents

Publication Publication Date Title
Gagolewski stringi: Fast and portable character string processing in R
US20210004361A1 (en) Parser for Schema-Free Data Exchange Format
JP4848317B2 (en) Database indexing system, method and program
US8645350B2 (en) Dictionary compilations
US20140108305A1 (en) Ranking for inductive synthesis of string transformations
Li et al. Optimal in-place suffix sorting
Belazzougui et al. Fast label extraction in the CDAWG
Noé et al. A coverage criterion for spaced seeds and its applications to support vector machine string kernels and k-mer distances
Amir et al. Longest common factor after one edit operation
Rajasekaran et al. An error correcting parser for context free grammars that takes less than cubic time
Grabowski A note on the longest common substring with k-mismatches problem
Kociumaka et al. Faster recovery of approximate periods over edit distance
Truong et al. Sensitive data detection with high-throughput neural network models for financial institutions
EP3413218A1 (en) Key-value memory networks
Manzini XBWT tricks
Hasan et al. Approximate string matching algorithms: a brief survey and comparison
Martin Minimal auxiliary Markov chains through sequential elimination of states
Ellert et al. Parallel external memory wavelet tree and wavelet matrix construction
Kim et al. Efficient enumeration of regular expressions for faster regular expression synthesis
Inenaga Suffix trees, DAWGs and CDAWGs for forward and backward tries
Song et al. Fast cartesian tree matching
Monjalet et al. Predicting file lifetimes with machine learning
Ueki et al. Longest common subsequence in at least k length order-isomorphic substrings
Gu et al. Fast multiple pattern cartesian tree matching
Ohlebusch et al. Computing the Burrows–Wheeler transform of a string and its reverse in parallel