Source-linked AI summary
Fuzzy Pattern Matching in Ordered Structures
Armen Kostanyan, Arevik Harmandayan
TL;DR
The paper studies how to find fuzzy-pattern occurrences when pattern symbols express graded properties, extending the problem from sequences to partially ordered structures. It uses trajectories as dynamic generalizations of KMP’s prefix function and represents the resulting algorithms as transition systems. The algorithms run in O(mn) time and O(m2) space for sequences, and O(mN) time and O(m2H) space for ordered trees.
Problem
The paper asks how fuzzy patterns can be matched in sequences and partially ordered structures when occurrences are defined by graded symbol properties.
Method
The approach dynamically processes trajectories that generalize the KMP prefix function, associating them with sequences or nodes in structured data.
Results
The sequence algorithm has time complexity O(mn) and space complexity O(m2), while the tree algorithm has time complexity O(mN) and space complexity O(m2H).
Takeaways & Limitations
The trajectory-based framework provides a unified representation for fuzzy matching in linear and hierarchical data structures.
Takeaways & Limitations
The hierarchical setting assumes a finite partially ordered structure is isomorphic to an ordered rooted tree, and the trajectory preliminaries assume a non-empty string of length no more than m.
Abstract
from arXiv · showhide
The problem of pattern matching, that is, finding all occurrences of a given pattern in a string, is one of the fundamental problems in computer science that has applications in many areas. In this paper, we consider fuzzy patterns, defined as sequences of fuzzy properties over the basic alphabet. We first consider fuzzy pattern matching for sequences of elements of the basic alphabet and then extend the problem to partially ordered sets of nodes labeled by elements of the basic alphabet. For sequences, we seek segments that match the pattern, whereas for partially ordered structures, we seek saturated chains of nodes that match the pattern. The key concept underlying the solutions to these problems is the notion of a trajectory, which generalizes the concept of the prefix function used in the Knuth--Morris--Pratt (KMP) algorithm. A trajectory is processed together with the corresponding data structure, allowing the proposed algorithms to be represented as transition systems whose states are trajectories for sequences and trajectories associated with nodes for partially ordered structures. The trajectory-based approach provides a unified framework for fuzzy pattern matching in various data structures.
1. Introduction
The paper addresses fuzzy pattern matching, where patterns express graded properties rather than exact characters, in both linear and partially ordered structures. It develops trajectory-based solutions that extend KMP-style matching to segments and saturated chains.
- Motivation: Exact matching is fundamental, but approximate matching addresses errors such as misspellings, mutations, and other variations.Approximate matching commonly uses Hamming or edit distance with a specified threshold.
- Motivation: Fuzzy matching represents how strongly matching conditions are satisfied instead of relying only on binary matches or fixed editing operations.The paper distinguishes this usage from approximate matching and defines fuzzy patterns as sequences of fuzzy properties over pattern symbols.
- Problem settings: The paper studies fuzzy pattern matching for text segments and for saturated chains in finite partially ordered structures.The first setting extends classical matching to fuzzy matching, while the second uses chains of labeled nodes as search objects.
- Core approach: Trajectories generalize the KMP prefix function by tracking compatibility between processed-sequence suffixes and fuzzy-pattern prefixes.The trajectory-based approach supports transition-system representations for both linear and structured matching.
- Contributions: The paper presents a trajectory-processing algorithm for linear structures and extends the framework to hierarchical structures represented by finite ordered rooted trees.The hierarchical solution processes trajectories associated with tree nodes while traversing the structure.
2. Preliminaries
The preliminaries define lists, strings, fuzzy symbols, fuzzy patterns, thresholded matching, borders, and trajectories. These concepts provide the formal objects used to represent graded pattern compatibility and its recursive history.
- Lists and strings: Lists are recursively defined sequences with a distinguished head and a remaining tail, together with standard construction and access operations.The operations include cons, head, and tail.
- Lists and strings: Strings are finite sequences over a finite alphabet Σ, including the empty string ε, with length denoted by |x|.The set of all such strings is written Σ∗, and |ε| = 0.
- Fuzzy symbols and patterns: A fuzzy subset assigns each element a membership degree in a linearly ordered domain bounded by 0 and 1.Membership degree 1 indicates certain inclusion, 0 indicates certain non-inclusion, and intermediate values represent graded inclusion.
- Fuzzy symbols and patterns: A fuzzy symbol is a fuzzy subset of the alphabet, and a fuzzy pattern is a non-empty finite sequence of fuzzy symbols.A character matches a fuzzy symbol with the symbol’s membership degree, assumed computable in O(1) time.
- Fuzzy symbols and patterns: A character µ-matches a fuzzy symbol when its membership degree is at least µ, with the definition extended componentwise to equal-length strings and patterns.This threshold determines whether a text segment satisfies the corresponding fuzzy properties.
- Borders and trajectories: A border is a proper suffix of a processed string that µ-matches the corresponding prefix of the fuzzy pattern, and LB(x) denotes the longest border.Borders capture suffix-prefix compatibility needed for trajectory construction.
- Borders and trajectories: A trajectory τ(x) is recursively built from the longest border of x, beginning with [ε] when no non-empty border exists.When LB(x) is non-empty, it is prepended to the trajectory of LB(x).
3. Fuzzy pattern matching in linear structures
The paper formulates fuzzy pattern matching in strings as finding all same-length segments that µ-match a fuzzy pattern, and proposes a trajectory-algebra algorithm modeled on KMP. The algorithm is correct, runs in O(mn) time, and uses O(m^2) space.
- Problem formulation: Fuzzy pattern matching finds every segment of length m in X that µ-matches pattern P, reporting occurrences by their end positions.The problem is called fuzzy L-matching.
- Trajectory algebra: Trajectory operations include constant-time promotion checks, O(m)-time promotion, and rollback by removing the trajectory’s head.These operations update the matching history as each input character is processed.
- Trajectory algebra: The FL-Matching algorithm dynamically processes trajectories that store relevant text suffixes µ-matching pattern prefixes, generalizing KMP’s prefix-function role.Unlike KMP preprocessing, trajectories depend on both the pattern and the processed text.
- Transition-system formulation: The transition-system formulation uses trajectories as states, with final states of size m signaling detected µ-occurrences.The transition function applies trajectory reduction and restarting rules during processing.
- Correctness: The trajectory at each inflection point contains all borders of the processed prefix, yielding the invariant head(τ_i) = LB(X[1..i]).The invariant supports the algorithm’s detection behavior and is established through rollback followed by at most one promotion.
- Correctness and complexity: Theorem 3.5 states that FL-Matching finds all and only the µ-occurrences of P in X, with O(mn) total time and O(m^2) space.The time bound follows from O(m) amortized cost per loop iteration across O(n) iterations; trajectory capacity determines the space bound.
4. Fuzzy pattern matching in hierarchical structures
The paper defines fuzzy pattern occurrences in ordered rooted trees as µ-matching descending chains and proposes preorder traversal with trajectories to find them. The FH-Matching algorithm is correct, with time O(mN) and space O(m^2H).
- Problem: A fuzzy pattern occurs in an ordered rooted tree when a descending chain of matching length has labels that µ-match the pattern.The problem identifies occurrences by their ending nodes.
- Algorithm: The FH-Matching algorithm traverses the tree in preorder while tracking trajectories associated with visited nodes.Its control component uses a stack of nodes and parent trajectories, while visitNode promotes a parent trajectory to the current node.
- Events: An event pairs a tree node with a trajectory and is realized when it stores that node’s trajectory rather than the parent’s rolled-back trajectory.The algorithm processes unrealized events, realizes them with visitNode, and adds corresponding child events to the stack.
- Transition system: The execution can be represented as a transition system whose states are events plus nil and whose configurations include the unrealized-event stack.Transitions process input labels, realize events, push successors, and pop the next unrealized event.
- Correctness: The algorithm finds all and only µ-occurrences of the fuzzy pattern in the hierarchical structure.Preorder visits every node once, and trajectory heads represent the longest suffix of the root-to-node label path that µ-matches a pattern prefix.
- Complexity: O(mN) time and O(m^2H) space characterize FH-Matching, where N is the node count and H is the tree height.Each node takes O(m) processing time, and the stack contains at most H elements requiring O(m^2) space each.
5. Conclusion
The paper develops fuzzy pattern matching for linear and hierarchical structures, using trajectories in KMP-like algorithms. It reports complexities of O(mn) time and O(m2) space for sequences, and O(mN) time and O(m2H) space for trees.
- Fuzzy patterns are sequences of fuzzy properties, and matching requires equal-length segments whose characters satisfy corresponding properties to a prescribed degree.
- Matching in linear structures: For linear structures, the KMP-like algorithm dynamically processes trajectories rather than a prefix-function array or integer state.Trajectories depend on both the pattern and the processed structure and are constructed during execution.
- Matching in linear structures: O(mn) time and O(m2) space are required for linear matching, where m and n are the pattern and sequence lengths.
- Matching in hierarchical structures: For hierarchical structures, preorder traversal tracks node-associated trajectories to find descending chains whose labels match the fuzzy pattern.The algorithm is represented as a labeled pushdown transition system whose states pair nodes with their current trajectories.
- Matching in hierarchical structures: O(mN) time and O(m2H) space are required for tree matching, where N is the node count and H is tree height.