Skip to content

README.en.md

Latest commit

 

History

History
667 lines (499 loc) · 29.1 KB

README.en.md

File metadata and controls

667 lines (499 loc) · 29.1 KB
Raw

FlowRegex - Automaton-Free Regular Expression Engine (POC)

Language: 🇯🇵 日本語 | 🇺🇸 English

FlowRegex is a revolutionary regular expression library that implements a fundamentally different approach to pattern matching - the "Flow Regex Method" - completely eliminating traditional automaton-based approaches.

Abstract

We present FlowRegex, a regular expression matching library inspired by Brzozowski's (1964) derivative theory of regular expressions, implemented using modern bitmask operations and function composition. Our approach addresses contemporary challenges through bitmask-based position set management and a novel functional composition methodology that eliminates the need for automaton construction.

A key achievement is theoretical immunity against ReDoS (Regular Expression Denial of Service) attacks, guaranteeing linear-time processing for any input. In experimental evaluation, our method completed processing in 0.0001 seconds for the attack pattern (a|a|b)*$ where Ruby's regex engine (Onigmo) timed out after 3 seconds, achieving over 29,000× performance improvement.

Furthermore, through fuzzy matching extensions, we enable revolutionary applications in genomic analysis. Unlike conventional heuristic methods such as BLAST, we provide theoretically complete similarity search in linear time, with high affinity for GPU parallel processing suggesting potential for performance improvements exceeding 1000× in the future.

⚠️ Important: This is a POC (Proof of Concept) version

  • The purpose is to demonstrate the theory, and performance is not optimized
  • Implementation prioritizes concept understanding and operation verification over practicality
  • Performance optimization and memory efficiency are left as future challenges

Revolutionary Features of Flow Regex Method

Core Innovation: Automaton-Free Architecture

FlowRegex is inspired by Brzozowski's derivative theory of regular expressions and implements this as a modern "position set transformation using bitmask operations", achieving extremely efficient and safe regular expression matching without any automaton construction.

Why Traditional Approaches Fall Short

Approach Construction Required Memory Usage ReDoS Risk Parallelization
Backtracking None Low High Poor
Thompson NFA Required Medium None Limited
DFA Required Very High None Good
FlowRegex None Low None Excellent

1. Function Composition: Position Set Transformation

  • In FlowRegex, each regex element (literal, concatenation, alternation, closure, etc.) is defined as a "transformation function" that processes specific input patterns.
  • These transformation functions receive "position sets (represented as bitmasks)" indicating which parts of the regex are currently matching candidates.
  • When processing a single character from the input string, based on character consumption, the received bitmask (starting point set) is transformed into a new bitmask (next activation point set).

2. Bitmask-Based Position Management: Efficient Parallel Processing

  • For elements like "alternation (|)" and "closure (*)" where multiple possibilities can exist simultaneously, FlowRegex calculates these possibilities individually and performs logical OR operations on multiple bitmasks to track all matching paths in parallel.
  • Crucially, FlowRegex processes all possible match starting positions simultaneously in a single pass, avoiding the O(N) multiplication factor that would occur from processing each starting position individually (where N = string length). However, this approach trades off the ability to directly identify match start positions, returning only match end positions (this constraint can be resolved through the two-stage matching approach described later).
  • This prevents the computational explosion problems of traditional backtracking and guarantees linear-time matching completion proportional to input string length.

3. No Backtracking: ReDoS Immunity

  • This "set transformation" approach represents regex processing states as finite bitmasks, preventing infinite loops or exponential computational complexity from backtracking problems.
  • This is the main reason FlowRegex has theoretical immunity against ReDoS (Regular Expression Denial of Service) attacks.

Comparison with Traditional Methods

Method Management Target Characteristics
Thompson NFA State set at current position Linear time, no backtracking
DFA Single state at current position Fast but potential state explosion
Backtracking Search path history High expressiveness but ReDoS vulnerability
Flow Regex Method Match end position set Function composition, parallel processing, ReDoS immunity

Installation

Ruby Version (POC)

require_relative 'lib/flow_regex'

C Implementation (Performance Verification - Limited Feature Set)

cd c_implementation
make
./test_runner  # Basic test execution

# Comprehensive test execution
./run_all_tests.sh

# OptimizedText optimization test
./test_with_optimization

# Recursive pattern test
./test_recursive_patterns

C Implementation Features:

  • Purpose: Performance verification of bitmask operations and MatchMask optimization proof-of-concept
  • Feature Scope: Subset of Ruby version (basic regex syntax only)
  • MatchMask Optimization: 1.6x〜2.5x performance improvement through OptimizedText
  • Shift Operation Elimination: Efficient bitmask operations in 64-bit word units
  • String Length Limit: 100,000 characters (FLOWREGEX_MAX_TEXT_LENGTH)
  • Test Implementation: Primarily for performance verification, not intended for production use

Note: The C implementation is for performance verification of features developed in Ruby. Please use the Ruby version for the complete feature set.

Basic Usage

# Basic matching
regex = FlowRegex.new("abc")
result = regex.match("xabcyz")
# => [4] (match ends at position 4)

# Multiple matches
regex = FlowRegex.new("a")
result = regex.match("banana")
# => [2, 4, 6] (end positions of each 'a' match)

# Alternation patterns
regex = FlowRegex.new("cat|dog")
result = regex.match("I have a cat and a dog")
# => [12, 22]

# Kleene closure
regex = FlowRegex.new("a*b")
result = regex.match("aaab")
# => [4]

# Debug mode
regex = FlowRegex.new("a*|b")
result = regex.match("aab", debug: true)
# Displays bitmask transformation process

MatchMask Optimization Features

FlowRegex provides acceleration through MatchMask pre-computation for single character literals.

Basic Usage

# Text optimization (pre-computation)
text = "ATGCATGCATGC" * 1000  # Large-scale DNA sequence
optimized_text = FlowRegex.optimize_text(text, alphabets: "ATGC")

# Matching with optimized text
regex = FlowRegex.new("ATG")
result = regex.match_optimized(optimized_text)
# => Faster than normal processing

# Using preset character sets
optimized_dna = FlowRegex.optimize_for_dna(dna_sequence)
optimized_rna = FlowRegex.optimize_for_rna(rna_sequence)
optimized_protein = FlowRegex.optimize_for_amino_acids(protein_sequence)

Performance Characteristics and Application Conditions

High effectiveness expected:

  • Genomic analysis: Large-scale data processing with 4 types of bases (ATGC)
  • Repeated processing: Multiple pattern searches on the same text
  • Large-scale data: Scale that can amortize pre-computation costs

Limitations:

  • Character class unsupported: Character classes like [AGC] are not optimized
  • Single character literals only: A|T|G|C is optimized, [ATGC] is not
  • Pre-computation cost: Limited effectiveness on small data

Measured Performance Data

# Comparison example: 780 characters processed 100 times
# Normal processing: 29.49ms
# Optimized processing: 26.05ms
# Improvement rate: 11.7% speedup

Note: POC version shows modest improvement rates, but C implementation achieves dramatic speedups exceeding 1000x.

Supported Regular Expression Syntax

Current POC version supports the following syntax:

Basic Syntax

  • Literals: a, b, c, etc.
  • Any character: . (any character except newline)
  • Concatenation: ab (a followed by b)
  • Alternation: a|b (a or b)
  • Grouping: (ab) (grouping)

Quantifiers

  • Kleene closure: a* (zero or more repetitions of a)
  • Plus: a+ (one or more repetitions of a)
  • Question: a? (zero or one occurrence of a)
  • Fixed count: a{3} (exactly 3 occurrences of a)
  • Range: a{2,4} (2 to 4 occurrences of a)
  • Lower bound: a{2,} (2 or more occurrences of a)

Character Classes

  • Digits: \d (0-9), \D (non-digits)
  • Whitespace: \s (whitespace characters), \S (non-whitespace)
  • Word characters: \w (alphanumeric_), \W (non-word characters)
  • Range specification: [a-z], [A-Z], [0-9]
  • Individual specification: [abc], [123]
  • Compound specification: [a-z0-9], [A-Za-z]
  • Character class escapes: [\d\s], [\w@], [a-z\d]
  • Negation: [^abc], [^\d\s] (characters other than specified)

Lookahead Operators (Intersection & Complement)

  • Positive lookahead: (?=B)A (intersection of A and B, both B and A match at same start position)
  • Negative lookahead: (?!B)A (A minus B, A only when B doesn't match at same start position)
  • Any position support: Works at positions other than string beginning
  • Multiple start positions: Accurate set operations at multiple start positions

Fuzzy Matching (Edit Distance Support)

  • Basic fuzzy match: fuzzy_match(text, max_distance: n)
  • Edit operations: Supports substitution, insertion, deletion
  • Distance limit: Detects matches within specified edit distance
  • Completeness guarantee: Exact solution, not heuristic

Escape Sequences

  • Newline: \n, Tab: \t
  • Carriage return: \r
  • Backslash: \\

Complex Pattern Examples

# Multiple quantifier combinations
FlowRegex.new("a+b?c*").match("aaabccc")
# => [1, 2, 3, 4, 5, 6, 7]

# Grouping with quantifiers
FlowRegex.new("(ab){2,3}").match("ababab")
# => [4, 6]

# Lookahead operators (intersection & complement)
FlowRegex.new("(?=ab)ab*c").match("abbbcd")
# => [5] (ab*c when starting with ab)

FlowRegex.new("(?!abc)ab*c").match("abbbcd")
# => [5] (ab*c when not starting with abc)

# Fuzzy matching (edit distance support)
FlowRegex.new("hello").fuzzy_match("helo", max_distance: 1)
# => {1=>[4]} (match with 1 character deletion)

FlowRegex.new("cat").fuzzy_match("bat", max_distance: 1)
# => {1=>[3]} (match with 1 character substitution)

Two-Stage Matching: Substring Extraction Support

Background and Challenge

Flow regex method had the constraint of "lack of match start positions". Traditional implementations only returned end positions, making substring extraction like text.match(/pattern/)[0] impossible.

Solution Through Two-Stage Approach

We adopted a "reverse calculation from end positions" approach:

Step 1: High-Speed Screening

end_positions = flow_regex_match(pattern, text)
# Identify end positions in O(n) time using flow regex method

Step 2: Reverse Analysis

for each end_pos in end_positions:
    # Reverse pattern to identify start position
    start_pos = reverse_match(pattern, text, end_pos)
    extract_substring(text, start_pos, end_pos)

Performance Characteristics

Computational Complexity: O(n + k×m)

  • Step 1: O(n) - Linear scan of entire string
  • Step 2: O(k×m) - k matches × average match length m

Effective Application Scenarios:

  • Large-scale data with few matches (k << n cases)
  • Rare pattern search in genomic analysis
  • Anomaly pattern extraction in large-scale logs

Comparison with Traditional Methods

Item Thompson NFA Two-Stage Flow Regex
Time complexity O(nm) O(n + k×m)
Substring extraction ✓ ✓
Large data processing Standard Advantageous when few matches

Implementation Architecture

FlowRegex
├── BitMask            # Bitmask operations
├── TrackedBitMask     # Start position tracking bitmask (for lookahead)
├── RegexElement       # Base class for transformation functions
├── Literal            # Character literal transformation function
├── Concat             # Concatenation transformation function (function composition)
├── Alternation        # Alternation transformation function (parallel processing)
├── KleeneStar         # Kleene closure transformation function (convergence processing)
├── Quantifier         # General quantifier transformation function
├── CharacterClass     # Character class transformation function
├── AnyChar            # Any character transformation function
├── PositiveLookahead  # Positive lookahead transformation function (intersection)
├── NegativeLookahead  # Negative lookahead transformation function (difference)
├── FuzzyBitMask       # 3D bitmask for fuzzy matching
├── FuzzyLiteral       # Fuzzy matching compatible character literal
├── FuzzyMatcher       # Fuzzy matching engine
├── Parser             # Regular expression parser (lookahead support)
├── Matcher            # Data flow engine
└── TwoStageMatcher    # Two-stage matching (substring extraction)

Limitations (POC Version)

  • String length limit: 10000 characters
  • Unicode support: Japanese (hiragana, katakana, kanji) operation confirmed
  • Backreferences (\1, \2) not supported
  • Lookahead computational complexity: Only increases to worst-case O(N²) when using lookahead operators (due to set operations at multiple start positions)
  • Lookbehind not supported
  • Non-greedy matching not supported
  • Position matching (^, $, \b) not supported

Performance Characteristics and Advantages

Scenarios Where Flow Regex Method Excels

  1. ReDoS attack patterns: Guarantees linear time even when traditional methods become exponential
  2. Complex nested patterns: Avoids backtracking explosion
  3. Large-scale data processing: High affinity with GPU parallel processing
  4. Multiple string simultaneous processing: Simultaneous processing instead of individual processing

Computational Complexity Comparison

Scenario DFA Thompson NFA Backtracking Flow Regex Method Two-Stage Flow
Simple patterns O(N) O(N×M) O(N×M) O(N×M) O(N + k×m)
ReDoS attacks O(N) O(N×M) O(2^N) O(N×M) O(N + k×m)
Multiple strings O(K×N) O(K×N×M) O(K×N×M) O(N×M) O(N + K×k×m)
Memory usage O(2^M) O(M) O(M) O(N) O(N)
Construction time O(2^M) O(M) O(M) O(M) O(M)

Characteristics and Strengths of Each Method

Method Strengths Constraints/Weaknesses Application Scenarios
DFA High-speed matching State explosion, high memory consumption Simple patterns, high-frequency processing
Thompson NFA Stability, ReDoS immunity Somewhat slow General regex processing
Backtracking High functionality (backreferences, etc.) ReDoS vulnerability Complex regex, small-scale data
Flow Regex Method Parallel processing, multiple strings Inferior in simple cases Large-scale parallel processing, GPU utilization
Two-Stage Flow Rare matches, substring extraction Degrades with many matches Genomic analysis, log monitoring

Scenarios Where FlowRegex Excels

  1. Large-scale data with rare pattern search (k << N)

    • Genomic analysis: Few mutation patterns in hundreds of millions of characters
    • Log monitoring: Few anomaly patterns in massive logs

  2. Simultaneous processing of multiple strings

    • Traditional: O(K×N×M) → FlowRegex: O(N×M)
    • Efficiency through parallel processing instead of individual processing of K strings

  3. Complete immunity to ReDoS attacks

    • Linear time guarantee even for patterns that make backtracking exponential
    • Safety in security-critical systems

  4. Affinity with GPU parallel processing

    • Natural parallelization of bitmask operations
    • Potential for 1000x+ performance improvements in the future

Note: POC version is for concept demonstration and may be inferior to optimized existing engines in simple cases. True value lies in overwhelming advantages in specific domains.

Revolutionary Applications in Fuzzy Matching

The most revolutionary application potential of the flow regex method lies in fuzzy matching (approximate search).

Revolutionary Value in Genomic Analysis

Current Challenges:

  • BLAST: Heuristic methods, limited completeness
  • BWA/Bowtie: Requires massive indices, high memory consumption
  • Traditional fuzzy matching: Risk of exponential time, ReDoS vulnerability

Advantages of Flow Regex Method:

  • Linear time guarantee: Stable performance regardless of mismatch count
  • No index required: Real-time processing possible
  • Complete GPU support: Expected 1000x+ parallelization effects
  • Theoretical completeness: Exact solution, not heuristic

Multi-dimensional Bitmask Extension

Traditional: BitMask[position] = 0/1
Extended: BitMask[position][mismatch_count] = 0/1

This extension enables simultaneous tracking of mismatch counts at each position, achieving edit distance-aware matching in linear time.

Application Fields

  1. Personalized genomic medicine: Real-time mutation detection, drug sensitivity prediction
  2. Infectious disease control: Immediate identification of viral variants, drug-resistant bacteria detection
  3. Evolutionary biology: Large-scale comparative genomic analysis, ancient DNA research
  4. Bioinformatics: Next-generation sequencer data analysis

Technical Feasibility

Implemented Features:

  • Phase 1: Substitution mismatches (implementation complete)
  • Phase 2: Addition of insertions/deletions (implementation complete)
  • Multi-dimensional bitmask: 2D management of position × mismatch count (implementation complete)

Future Extensions:

  • Phase 3: GPU parallel implementation (large-scale data support)
  • Phase 4: Validation and optimization with real genomic data

This innovation has the potential to bring new paradigms to computational biology.

High-Performance Parallel Architecture

MatchMask Method (Implemented)

We have implemented an advanced parallelization technique that further develops the flow regex method. This technique achieves dramatic performance improvements by completely eliminating traditional shift operations and efficiently reusing pre-computed MatchMasks and bit sequences.

Core Technology: MatchMask Pre-computation

String S (length N): "abcabc"
MatchMask for 'a': [1,0,0,1,0,0]
MatchMask for 'b': [0,1,0,0,1,0]
MatchMask for 'c': [0,0,1,0,0,1]

Literal L('a') processing:
Mout = (Min AND Ma) << 1  →  Mout = Min AND Ma_offset

Complete Elimination of Shift Operations

Traditional Problem:

// Expensive shift operations
result = (input & match_mask) << 1;

Revolutionary Solution:

// Logical shift through offset management
result = input & match_mask_with_offset;
current_offset++;  // Logical position management

Efficient Bit Sequence Reuse

Staged Processing of Kleene Closure:

// "a*" processing - efficient management with 2 bit sequences
offset_mask_t current = {input_mask, offset=0};
offset_mask_t result = {input_mask, offset=0};  // 0 matches

do {
    offset_mask_t next = process_literal(current, 'a');
    result.bits |= next.bits;  // Accumulation
    current = next;            // Bit sequence reuse
} while (has_new_matches(next));

Efficient Alternation Processing:

// "a|b" - parallel processing at same offset
offset_mask_t left = process_literal(input, 'a');
offset_mask_t right = process_literal(input, 'b');
result.bits = left.bits | right.bits;  // Simple OR combination

Application Conditions and Effective Scenarios

✅ High effectiveness expected

Genomic Analysis (Optimal):

  • Character types: Only 4 types (A,T,G,C) → Extremely efficient pre-scanning
  • String length: Millions to hundreds of millions of characters
  • Processing frequency: Repeated analysis on same data
  • Effect: Pre-scanning cost << Processing speedup

Repeated processing on same string:

  • Log monitoring: Real-time anomaly detection
  • Regular analysis: Repeated pattern search in batch processing
  • Effect: Complete amortization of pre-computation costs

Parallel processing of large numbers of strings:

  • Simultaneous processing of thousands to tens of thousands of strings
  • GPU parallel processing: Expected 1000x+ performance improvements
  • Memory efficiency: Optimization through continuous access patterns

⚠️ Limited effectiveness scenarios

One-time processing:

  • Pre-computation costs may exceed processing time
  • Traditional methods advantageous for small-scale data

Many character types:

  • Full ASCII (256 types) increases pre-scanning costs
  • Selective application to frequent characters only is effective

Implementation Strategy

Staged Application

// Phase 1: Target frequent characters only
char frequent_chars[] = {'a', 'e', 'i', 'o', 'u', ' ', '\n'};
for (char c : frequent_chars) {
    precompute_match_mask(text, c);
}

// Phase 2: All character support (conditional)
if (text_reuse_count > threshold) {
    precompute_all_match_masks(text);
}

Application Decision Algorithm

typedef struct {
    size_t text_length;
    size_t unique_chars;
    size_t expected_matches;
    bool is_repeated_processing;
} optimization_context_t;

bool should_use_match_mask(optimization_context_t* ctx) {
    // Genomic data: Always apply
    if (ctx->unique_chars <= 4) return true;

    // Repeated processing: Threshold judgment
    if (ctx->is_repeated_processing &&
        ctx->expected_matches > REPEAT_THRESHOLD) return true;

    // One-time: Careful judgment
    return (ctx->text_length > LARGE_TEXT_THRESHOLD &&
            ctx->expected_matches > SINGLE_USE_THRESHOLD);
}

Performance Characteristics

Theoretical Advantages

  • Mathematical equivalence: Guarantees exactly same results as traditional methods
  • Shift operation elimination: Significant reduction in CPU instructions
  • Parallelization affinity: Complete compatibility with SIMD/GPU processing
  • Memory efficiency: Optimization through continuous access patterns

Practical Constraints

  • Pre-computation cost: O(N×character_types×MAX_OFFSET)
  • Memory usage: character_types × MAX_OFFSET × string_length bitmasks
  • Application decision: Dynamic selection based on processing frequency and data characteristics

Characteristics by Application Field

Ideal conditions for genomic analysis:

Memory usage: 4 characters × 100 offsets × (1M characters/64) ≈ 6.25KB
Processing speed: Expected 100-1000x improvement over traditional
Application value: Extremely high

General text processing:

Memory usage: 256 characters × MAX_OFFSET × (string_length/64)
Processing speed: Significant improvement depending on conditions
Application value: Depends on data characteristics and processing frequency

This parallelization technique enables revolutionary performance improvements, especially in genomic analysis. Under ideal conditions with 4 types of base pairs, it can achieve efficiency far superior to traditional methods.

Future Extension Plans

High Priority: Differential-Based Optimization of Kleene Closure

  • Current issue: Recomputes already processed positions by applying internal elements to entire bitmask each time
  • Differential approach: Incremental processing using only newly added bits as input for next iteration
  • Expected effect: Computational complexity reduction from O(k×n×m) → O(Σ(new bit count×m))
  • Application conditions: Large-scale data + low-density matching + complex internal elements
  • Implementation challenges:
    • Increased implementation complexity and bug risk
    • Memory overhead (2-3x BitMask usage)
    • Potential performance degradation on small-scale data
    • Complexity of application decision logic
  • Recommended strategy: Hybrid approach (switch between traditional methods based on conditions)

High Priority: Parallel Architecture Implementation

  • MatchMask method implementation: CPU SIMD compatible version development
  • GPU parallel processing: Large-scale parallelization through CUDA/OpenCL implementation
  • Hybrid implementation: Automatic decision and switching based on data characteristics
  • Profiling: Automation of optimization decisions

Fuzzy Matching Feature Extensions

  • Full application to genomic analysis: SNP detection, variant identification, personal genome analysis
  • Performance optimization: Speedup from current POC implementation to practical level
  • Memory efficiency: Memory optimization for large-scale genomic data support
  • Real-time mutation detection: Practical high-speed fuzzy search without indices

Technical Extensions

  • Sparse bitmaps: Memory optimization for large-scale fuzzy matching
  • Approximate search engine: Applications to natural language processing and information retrieval
  • Distributed processing support: Large-scale parallel processing in cluster environments
  • Memory optimization: Efficiency through compression techniques

Test Execution

ruby test/test_flow_regex.rb

Example Execution

ruby examples/basic_usage.rb

Theoretical Background

The flow regex method is based on the following mathematical concepts:

  1. Function composition: Combination of regex elements through f ∘ g
  2. Fixed point theory: Convergence processing of Kleene closure
  3. Set operations: Position set operations through bitwise OR/AND
  4. Parallel processing: Simultaneous execution of multiple match paths

This technique realizes a new regex processing paradigm that doesn't depend on traditional automaton theory.

Theoretical Foundation and Prior Research

Brzozowski Derivative Theory (1964)

The theoretical foundation of this research is based on the classic 1964 study by Janusz A. Brzozowski:

Janusz A. Brzozowski (1964). "Derivatives of Regular Expressions". Journal of the ACM 11(4), 481-494.
Paper link: https://dl.acm.org/doi/10.1145/321239.321249

This research introduced the concept of "derivatives" of regular expressions, showing that direct regex matching without automaton construction is possible by recursively defining derivatives of regular expressions with respect to characters. Particularly important is that this theory naturally supports intersection and complement operations.

Development to Modern Implementations

Implementation Using Regular Expression Functions (2003)

Atsushi Yamamoto (2003). "Extension of Regular Expressions Using Regular Expression Functions and Their Application to Pattern Matching". IPSJ Journal 44(7), 1756-1765.
Paper link: https://cir.nii.ac.jp/crid/1050564287837265792

Research that implemented Brzozowski theory as "functions that transform sets of string end positions" and aimed to make regex processing practical through function composition.

High-Performance Derivative-Based Implementation (2025)

Ian Erik Varatalu, Margus Veanes, and Juhan Ernits (2025). "RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement, and Restricted Lookarounds". Proc. ACM Program. Lang. 9, POPL, Article 1.
Paper link: https://www.microsoft.com/en-us/research/wp-content/uploads/2025/01/popl25-p2-final.pdf

Latest research that symbolically implements Brzozowski derivatives, achieving high-performance intersection, complement, and restricted lookahead operations.

Position of This Research

FlowRegex implements Brzozowski's (1964) derivative theory using modern bitmask operations, addressing the following contemporary challenges:

  1. Complete prevention of ReDoS attacks: Safe for any input through linear time guarantee of derivative theory
  2. Application to genomic analysis: High-speed similarity search for DNA sequences through fuzzy matching extensions
  3. GPU parallel processing support: Applicable to large-scale data processing through parallelism of bitmask operations

Modern Significance of the Theory

Why Brzozowski's 60-year-old theory is important in modern times:

  • Security: Theoretically safe regex engines needed in modern times when ReDoS attacks are becoming serious
  • Big data: Predictable linear time performance important in large-scale data processing
  • Bioinformatics: High-speed similarity search technology needed due to explosive increase in genomic data
  • Parallel processing: Parallelizable algorithms important in modern era where GPU/multi-core processing is common

License

TBD (To Be Determined)

Author

Atsushi Yamamoto