[go: up one dir, main page]

Golan et al., 2019 - Google Patents

Dynamic dictionary matching in the online model

Golan et al., 2019

View PDF
Document ID
18394308123536039562
Author
Golan S
Kociumaka T
Kopelowitz T
Porat E
Publication year
Publication venue
Workshop on Algorithms and Data Structures

External Links

Snippet

In the classic dictionary matching problem, the input is a dictionary of patterns D={P 1, P 2,…, P k} and a text T, and the goal is to report all the occurrences in T of every pattern from D. In the dynamic version of the dictionary matching problem, patterns may be either added …
Continue reading at www.mimuw.edu.pl (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
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/50—Monitoring users, programs or devices to maintain the integrity of platforms, e.g. of processors, firmware or operating systems
    • G06F21/55—Detecting local intrusion or implementing counter-measures
    • G06F21/56—Computer malware detection or handling, e.g. anti-virus arrangements
    • G06F21/562—Static detection
    • G06F21/563—Static detection by source code analysis
    • 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
    • G06F17/2247—Tree structured documents; Markup, e.g. Standard Generalized Markup Language [SGML], Document Type Definition [DTD]
    • 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
    • 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/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
    • G06F8/00—Arrangements for software engineering
    • G06F8/40—Transformations of program code
    • G06F8/41—Compilation
    • G06F8/42—Syntactic analysis
    • 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/30908—Information retrieval; Database structures therefor; File system structures therefor of semistructured data, the undelying structure being taken into account, e.g. mark-up language structure data
    • 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/2705—Parsing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/70—Software maintenance or management
    • G06F8/75—Structural analysis for program understanding
    • 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
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/745—Address table lookup or address filtering
    • H04L45/7457—Address table lookup or address filtering using content-addressable memories [CAM]

Similar Documents

Publication Publication Date Title
US7512634B2 (en) Systems and methods for processing regular expressions
JP6557334B2 (en) Access classification device, access classification method, and access classification program
Weideman et al. Analyzing matching time behavior of backtracking regular expression matchers by using ambiguity of NFA
US8407245B2 (en) Efficient string pattern matching for large pattern sets
US20120221494A1 (en) Regular expression pattern matching using keyword graphs
US20050240999A1 (en) Method and system for adaptive rule-based content scanners for desktop computers
US8386530B2 (en) Systems and methods for processing regular expressions
US20250021755A1 (en) Regular expression searching
US20120158768A1 (en) Decomposing and merging regular expressions
EP4024251B1 (en) Method for verifying vulnerabilities of network devices using cve entries
US10467272B2 (en) Detecting longest regular expression matches
Rajasekaran et al. An error correcting parser for context free grammars that takes less than cubic time
Goto et al. LZD factorization: Simple and practical online grammar compression with variable-to-fixed encoding
Golan et al. Dynamic dictionary matching in the online model
Mieno et al. Minimal unique substrings and minimal absent words in a sliding window
US8380795B2 (en) Method of filtering sections of a data stream
Macedo et al. Exploiting partial knowledge for efficient model analysis
Bille et al. Compressed subsequence matching and packed tree coloring
Bille et al. Fast practical compression of deterministic finite automata
Fujisato et al. The parameterized position heap of a trie
Mamouras et al. Static Analysis for Checking the Disambiguation Robustness of Regular Expressions
Alzamel et al. Efficient computation of sequence mappability
Golan Bar-Ilan University, Ramat-Gan, Israel {golansh1, porately}@ cs. biu. ac. il, kociumaka@ mimuw. edu. pl, kopelot@ gmail. com
Keeler et al. Width measures of alternating finite automata
Mrykhin et al. The hardest LL (k) language