Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Online Pattern Matching for String Edit Distance with Moves   Edit distance with moves (EDM) is a string-to-string distance measure that
includes substring moves in addition to ordinal editing operations to turn one
string to the other. Although optimizing EDM is intractable, it has many
applications especially in error detections. Edit sensitive parsing (ESP) is an
efficient parsing algorithm that guarantees an upper bound of parsing
discrepancies between different appearances of the same substrings in a string.
ESP can be used for computing an approximate EDM as the L1 distance between
characteristic vectors built by node labels in parsing trees. However, ESP is
not applicable to a streaming text data where a whole text is unknown in
advance. We present an online ESP (OESP) that enables an online pattern
matching for EDM. OESP builds a parse tree for a streaming text and computes
the L1 distance between characteristic vectors in an online manner. For the
space-efficient computation of EDM, OESP directly encodes the parse tree into a
succinct representation by leveraging the idea behind recent results of a
dynamic succinct tree. We experimentally test OESP on the ability to compute
EDM in an online manner on benchmark datasets, and we show OESP's efficiency.

4
The categories of this paper are: cond-mat
20
The categories of this paper are: acc-phys
29
The categories of this paper are: funct-an
26
The categories of this paper are: bayes-an
35
The categories of this paper are: mtrl-th
8
The categories of this paper are: hep-ex
0
The categories of this paper are: hep-ph
21
The categories of this paper are: adap-org
27
The categories of this paper are: comp-gas
37
The categories of this paper are: supr-con
25
The categories of this paper are: patt-sol
10
The categories of this paper are: q-bio
11
The categories of this paper are: hep-lat
5
The categories of this paper are: gr-qc
34
The categories of this paper are: chem-ph
19
The categories of this paper are: eess