# The Art of Embedding Fusion: Optimizing Hate Speech Detection

Mohammad Aflah Khan, Neemesh Yadav, Mohit Jain & Sanyam Goyal
Indraprastha Institute of Information Technology
New Delhi, India
<EMAIL_ADDRESS>

###### Abstract

Hate speech detection is a challenging natural language processing task that
requires capturing linguistic and contextual nuances. Pre-trained language
models (PLMs) offer rich semantic representations of text that can improve
this task. However there is still limited knowledge about ways to effectively
combine representations across PLMs and leverage their complementary
strengths. In this work, we shed light on various combination techniques for
several PLMs and comprehensively analyze their effectiveness. Our findings
show that combining embeddings leads to slight improvements but at a high
computational cost and the choice of combination has marginal effect on the
final outcome. We also make our codebase public here.

##  1 Introduction

Recent advances in deep learning have been significantly influenced by the
introduction of pretrained models Zhou et al. (2023), which serve as a strong
foundation for various downstream tasks such as classification, generation,
and sequence labeling. In particular, these models generate dense vector
representations of input text that have been effective across a wide range of
models, replacing older techniques such as TF-IDF, Word2Vec, and GLoVe. The
success of pretrained language models (PLMs) has led to the development of
domain-specific versions, such as HateBERT Caselli et al. (2020) and BERTweet
Nguyen et al. (2020), which use the same architecture as BERT Devlin et al.
(2019). In this study we aim to identify the most effective model or
combination of models (BERT, HateBERT, and BERTweet) for hate speech
classification tasks.

##  2 Related Work

Hate speech detection has been a prevalent task in the NLP community for a
long time. Various techniques have been used to recognize hate speech, such as
combining n-gram and linguistic features with machine learning models Davidson
et al. (2017), contrastive learning Kim et al. (2022), and retraining language
models on hateful data Caselli et al. (2020). Pre-trained language models
(PLMs) have been successful in generating context-rich word embeddings, which
can be combined to generate sentence embeddings using different methods like
pooling embeddings or training siamese networks Reimers & Gurevych (2019).
However, as different PLMs were trained on different datasets and have
different sizes, their capabilities are expected to differ. Although previous
works have shown that combining embeddings from different sources can boost
performance (Lester et al. (2020), Badri et al. (2022)), no work has compared
all the well-known ways to combine word embeddings for hate speech detection.

Overall, hate speech detection is an important task in NLP, and various
techniques have been used to achieve it. PLMs have been successful in
generating context-rich word embeddings, but their capabilities differ
depending on their training dataset and size. Combining embeddings from
different sources has been shown to improve performance, but there is
currently no work that compares all the well-known ways to combine word
embeddings for hate speech detection.

##  3 Dataset

Three datasets are utilized in this study: OLID Zampieri et al. (2019) for
offensive vs non-offensive Twitter post classification, Latent Hatred
ElSherief et al. (2021) for implicit hate vs explicit hate vs non hate
classification, and DynaHate Vidgen et al. (2021) for hate vs non-hate
classification with human-in-the-loop generated sentences. Dataset statistics
are provided in A.1 and preprocessing steps are outlined in A.2.

##  4 Methodology

For each sentence we first produce an embedding using BERT, HateBERT as well
as BERTweet by using pooler output. Pooler output is the last layer hidden-
state of the first token of the sequence (classification token), further
processed by a Linear layer and a Tanh activation function. This is a model
endpoint exposed under the HuggingFace API, Wolf et al. (2020).

We conduct experiments using three random seeds, utilizing five combination
strategies (addition, concatenation, interleaving, multiplication, and random
interleaving) to combine two or all three embeddings. Each standalone/combined
embedding is used to train a multi-layer perceptron (MLP) for the
classification task using five-fold cross-validation. We anticipate
Concatenation and Interleave methods to perform similarly, as MLPs do not take
positional information. We expect random interleaving to perform poorly, as
embeddings become degenerate and dimensions lose meaning. Finally, we expect
combining multiple embeddings to outperform using a single embedding. More
detailed explanations of these methods can be found in A.3 and A.4.

Model | Accuracy
---|---
bert bertweet hatebert interleaved | 0.716
bert bertweet hatebert concat | 0.705
hatebert bertweet interleaved | 0.704
hatebert bertweet concat | 0.700
bert hatebert concat | 0.693
Table 1: DynaHate Results: Top 5 Combinations

Model | Accuracy
---|---
hatebert bertweet interleaved | 0.703
hatebert bertweet multiplied | 0.700
bert bertweet hatebert concat | 0.700
bert bertweet hatebert multiplied | 0.700
bert bertweet interleaved | 0.700
Table 2: LatentHatred Results: Top 5 Combinations

##  5 Results

From Tables 2, 2, we observe that the performances of the classifiers are very
similar irrespective of the combination of embeddings. Only random
interleaving is a poor choice as it makes the embeddings degenerate.
Combinations where the dimensionality increases seem to be marginally better
which can be attributed to the fact that it brings in more data for the model
to extrapolate relations. In all the three tables 6, 7, and 8, the top 3
methods of combination remain to be interleaving, concatenation and
multiplication of embeddings, but only marginally. In general having more than
one embedding seems to be marginally better and amongst the 3 models HateBERT
and BERTweet are more likely to perform better which can be attributed to
their training on Hateful and Twitter data.

##  6 Conclusion

The results111Due to the paper’s length constraints, we have shown the results
and a graphical representation of these results for all embedding combinations
in A.5. indicate that concatenation and interleaving have similar performance
as expected. Addition, a commonly used embedding combination, also shows good
performance. Although multiplication is rarely used, its performance is
comparable to addition across tasks. Therefore, in low-compute settings, an
embedding combination such as addition can be used to achieve similar
performance as concatenation without increasing the input dimensionality by
2-3x, which would require more training time and resources.

#### Acknowledgements

We express our gratitude to Devansh Gupta & Rishi Singhal for their valuable
feedback on the initial drafts of our paper. We also extend our thanks to Dr.
Md. Shad Akhtar for providing guidance during the early stages of this work
when it was just a course project.

#### URM Statement

It is acknowledged by the authors that all of the authors involved in this
work meet the URM criteria of the ICLR 2023 Tiny Papers Track.

## References

  * Badri et al. (2022) Nabil Badri, Ferihane Kboubi, and Anja Habacha Chaibi.  Combining fasttext and glove word embedding for offensive and hate speech text detection.  _Procedia Computer Science_ , 207:769–778, 2022.  ISSN 1877-0509.  doi: https://doi.org/10.1016/j.procs.2022.09.132.  URL https://www.sciencedirect.com/science/article/pii/S1877050922010134.  Knowledge-Based and Intelligent Information & Engineering Systems: Proceedings of the 26th International Conference KES2022.
  * Caselli et al. (2020) Tommaso Caselli, Valerio Basile, Jelena Mitrović, and Michael Granitzer.  Hatebert: Retraining bert for abusive language detection in english.  _arXiv preprint arXiv:2010.12472_ , 2020.
  * Davidson et al. (2017) Thomas Davidson, Dana Warmsley, Michael Macy, and Ingmar Weber.  Automated hate speech detection and the problem of offensive language.  In _Proceedings of the international AAAI conference on web and social media_ , volume 11, pp. 512–515, 2017.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 4171–4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1423.  URL https://aclanthology.org/N19-1423.
  * ElSherief et al. (2021) Mai ElSherief, Caleb Ziems, David Muchlinski, Vaishnavi Anupindi, Jordyn Seybolt, Munmun De Choudhury, and Diyi Yang.  Latent hatred: A benchmark for understanding implicit hate speech.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pp. 345–363, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.emnlp-main.29.  URL https://aclanthology.org/2021.emnlp-main.29.
  * Kim et al. (2022) Youngwook Kim, Shinwoo Park, and Yo-Sub Han.  Generalizable implicit hate speech detection using contrastive learning.  In _Proceedings of the 29th International Conference on Computational Linguistics_ , pp. 6667–6679, Gyeongju, Republic of Korea, October 2022. International Committee on Computational Linguistics.  URL https://aclanthology.org/2022.coling-1.579.
  * Lester et al. (2020) Brian Lester, Daniel Pressel, Amy Hemmeter, Sagnik Ray Choudhury, and Srinivas Bangalore.  Multiple word embeddings for increased diversity of representation.  _arXiv preprint arXiv:2009.14394_ , 2020.
  * Nguyen et al. (2020) Dat Quoc Nguyen, Thanh Vu, and Anh Tuan Nguyen.  BERTweet: A pre-trained language model for English tweets.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pp. 9–14, Online, October 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.emnlp-demos.2.  URL https://aclanthology.org/2020.emnlp-demos.2.
  * Reimers & Gurevych (2019) Nils Reimers and Iryna Gurevych.  Sentence-BERT: Sentence embeddings using Siamese BERT-networks.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pp. 3982–3992, Hong Kong, China, November 2019. Association for Computational Linguistics.  doi: 10.18653/v1/D19-1410.  URL https://aclanthology.org/D19-1410.
  * Vidgen et al. (2021) Bertie Vidgen, Tristan Thrush, Zeerak Waseem, and Douwe Kiela.  Learning from the worst: Dynamically generated datasets to improve online hate detection.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pp. 1667–1682, Online, August 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.acl-long.132.  URL https://aclanthology.org/2021.acl-long.132.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pp. 38–45, Online, October 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.emnlp-demos.6.  URL https://aclanthology.org/2020.emnlp-demos.6.
  * Zampieri et al. (2019) Marcos Zampieri, Shervin Malmasi, Preslav Nakov, Sara Rosenthal, Noura Farra, and Ritesh Kumar.  Predicting the type and target of offensive posts in social media.  _arXiv preprint arXiv:1902.09666_ , 2019.
  * Zhou et al. (2023) Ce Zhou, Qian Li, Chen Li, Jun Yu, Yixin Liu, Guangjing Wang, Kai Zhang, Cheng Ji, Qiben Yan, Lifang He, et al.  A comprehensive survey on pretrained foundation models: A history from bert to chatgpt.  _arXiv preprint arXiv:2302.09419_ , 2023.

##  Appendix A Appendix

###  A.1 Dataset Statistics

Split | Offensive (OFF) | Not Offensive (NOT)
---|---|---
Train | 3485 | 7107
Dev | 915 | 1733
Test | 240 | 620
Table 3: OLID Dataset Statistics Split | Hate | Not Hate
---|---|---
Train | 17740 | 15184
Dev | 2167 | 1933
Test | 2268 | 1852
Table 4: DynaHate Dataset Statistics Split | Implicit Hate | Explicit Hate | Not Hate
---|---|---|---
Train | 3991 | 590 | 7501
Dev | 1356 | 228 | 2444
Test | 1753 | 271 | 3346
Table 5: LatentHatred Dataset Statistics

###  A.2 Data Preprocessing

We follow the following steps for dataset preprocessing -

  1. 1.

Remove emojis

  2. 2.

Remove stray punctuations

  3. 3.

Replace URLs and HTML Tags with a placeholder

  4. 4.

Replace usernames with a placeholder

  5. 5.

Remove extra whitespaces

###  A.3 Embeddings Combination Methods

  1. 1.

Addition: Simply adding the embeddings

  2. 2.

Multiplication: Element wise multiplication of the embeddings

  3. 3.

Interleaving: Interleaving the embeddings to form a common embedding. For
instance if the embeddings are [1,2,3] & [4,5,6] the interleaved output would
be [1,4,2,5,3,6]

  4. 4.

Concatenation: Simply concatenate the embeddings

  5. 5.

Random Interleaving: Instead of interleaving in an ordered fashion we
interleave in a random fashion for each sample. This therefore acts as a
baseline as the dimensions do not align across samples

###  A.4 Design Choices for the Models

For all our experiments we use the MLPClassifier API from scikit-learn. We use
the following parameters for Grid Search -

  1. 1.

”hidden_layer_sizes”: [(128), (128,64)]

  2. 2.

”activation”: [”relu”]

  3. 3.

”solver”: [”adam”]

  4. 4.

”learning_rate_init”: [0.001, 0.0001]

  5. 5.

”learning_rate”: [”adaptive”]

  6. 6.

”early_stopping”: [True]

  7. 7.

”max_iter”: [10000]

We use 3 Random Seeds - 3, 7, 42

###  A.5 Results

We request the reader to refer to Tables 6, 7, and 8 given below, for
quantitative information regarding the scores for all the embedding
combinations reported over the Accuracy and Macro F1 metrics.

For a graphical representation of these scores, kindly refer to the Figures 1,
2 for results over the DynaHate dataset, 3, 4 for results over the
LatentHatred dataset, and 5, 6 for the OLID dataset.

Embedding Combination | Accuracy | Macro F1
---|---|---
bert bertweet hatebert interleaved | 0.716 | 0.710
bert bertweet hatebert concat | 0.705 | 0.701
hatebert bertweet interleaved | 0.704 | 0.698
hatebert bertweet concat | 0.700 | 0.695
bert hatebert concat | 0.693 | 0.687
bert hatebert interleaved | 0.692 | 0.686
bert bertweet hatebert added | 0.687 | 0.684
hatebert bertweet added | 0.687 | 0.680
bert hatebert added | 0.687 | 0.681
hatebert | 0.686 | 0.681
hatebert bertweet multiplied | 0.684 | 0.682
bert hatebert multiplied | 0.682 | 0.675
bert bertweet concat | 0.678 | 0.671
bert bertweet interleaved | 0.678 | 0.664
bert bertweet hatebert multiplied | 0.677 | 0.674
bert bertweet added | 0.668 | 0.662
bert | 0.663 | 0.652
bert bertweet multiplied | 0.663 | 0.657
bertweet | 0.642 | 0.638
bert hatebert randomlycombined | 0.550 | 0.355
bert bertweet hatebert randomlycombined | 0.550 | 0.360
bert bertweet randomlycombined | 0.549 | 0.362
hatebert bertweet randomlycombined | 0.548 | 0.369
Table 6: DynaHate Results for all embedding combinations. Embedding Combination | Accuracy | Macro F1
---|---|---
hatebert bertweet interleaved | 0.703 | 0.494
hatebert bertweet multiplied | 0.700 | 0.469
bert bertweet hatebert concat | 0.700 | 0.517
bert bertweet hatebert multiplied | 0.700 | 0.486
bert bertweet interleaved | 0.700 | 0.486
hatebert bertweet concat | 0.699 | 0.465
bertweet | 0.699 | 0.482
bert bertweet hatebert added | 0.697 | 0.478
bert bertweet concat | 0.697 | 0.474
bert bertweet multiplied | 0.696 | 0.493
bert bertweet hatebert interleaved | 0.695 | 0.477
bert hatebert concat | 0.694 | 0.480
hatebert bertweet added | 0.693 | 0.476
bert hatebert multiplied | 0.693 | 0.457
bert bertweet added | 0.690 | 0.452
bert hatebert added | 0.689 | 0.463
bert hatebert interleaved | 0.686 | 0.451
hatebert | 0.684 | 0.440
bert | 0.683 | 0.430
bert bertweet randomlycombined | 0.623 | 0.256
bert bertweet hatebert randomlycombined | 0.623 | 0.256
bert hatebert randomlycombined | 0.623 | 0.256
hatebert bertweet randomlycombined | 0.623 | 0.257
Table 7: LatentHatred Results for all embedding combinations. Embedding Combination | Accuracy | Macro F1
---|---|---
bert bertweet interleaved | 0.813 | 0.732
bert bertweet concat | 0.812 | 0.738
bert bertweet hatebert interleaved | 0.808 | 0.719
bert bertweet hatebert concat | 0.805 | 0.721
bert bertweet hatebert added | 0.802 | 0.707
bert hatebert multiplied | 0.802 | 0.700
hatebert bertweet concat | 0.802 | 0.722
hatebert bertweet multiplied | 0.801 | 0.720
bert bertweet added | 0.797 | 0.700
bert hatebert interleaved | 0.797 | 0.711
bert hatebert concat | 0.795 | 0.702
hatebert bertweet interleaved | 0.795 | 0.703
bert hatebert added | 0.792 | 0.685
bert bertweet multiplied | 0.792 | 0.698
bert bertweet hatebert multiplied | 0.792 | 0.696
bert | 0.791 | 0.704
hatebert | 0.790 | 0.691
bertweet | 0.783 | 0.680
hatebert bertweet added | 0.777 | 0.663
bert hatebert randomlycombined | 0.721 | 0.420
bert bertweet randomlycombined | 0.721 | 0.419
bert bertweet hatebert randomlycombined | 0.721 | 0.419
hatebert bertweet randomlycombined | 0.721 | 0.419
Table 8: OLID Results for all embedding combinations. Figure 1: Accuracy for
DynaHate Figure 2: Macro F1 for DynaHate Figure 3: Accuracy for Latent Hatred
Figure 4: Macro F1 for Latent Hatred Figure 5: Accuracy for OLID Figure 6:
Macro F1 for OLID


# The Parameterized Suffix Tray

Noriki Fujisato1 1Department of Informatics, Kyushu University, Fukuoka, Japan
{noriki.fujisato, yuto.nakashima, inenaga<EMAIL_ADDRESS>
2PRESTO, Japan Science and Technology Agency, Kawaguchi, Japan
3M&D Data Science Center, Tokyo Medical and Dental University, Tokyo, Japan
<EMAIL_ADDRESS>Yuto Nakashima1 1Department of Informatics, Kyushu
University, Fukuoka, Japan
{noriki.fujisato, yuto.nakashima, inenaga<EMAIL_ADDRESS>
2PRESTO, Japan Science and Technology Agency, Kawaguchi, Japan
3M&D Data Science Center, Tokyo Medical and Dental University, Tokyo, Japan
<EMAIL_ADDRESS>Shunsuke Inenaga1,2 1Department of Informatics, Kyushu
University, Fukuoka, Japan
{noriki.fujisato, yuto.nakashima, inenaga<EMAIL_ADDRESS>
2PRESTO, Japan Science and Technology Agency, Kawaguchi, Japan
3M&D Data Science Center, Tokyo Medical and Dental University, Tokyo, Japan
<EMAIL_ADDRESS>Hideo Bannai3 1Department of Informatics, Kyushu
University, Fukuoka, Japan
{noriki.fujisato, yuto.nakashima, inenaga<EMAIL_ADDRESS>
2PRESTO, Japan Science and Technology Agency, Kawaguchi, Japan
3M&D Data Science Center, Tokyo Medical and Dental University, Tokyo, Japan
<EMAIL_ADDRESS>Masayuki Takeda1 1Department of Informatics, Kyushu
University, Fukuoka, Japan
{noriki.fujisato, yuto.nakashima, inenaga<EMAIL_ADDRESS>
2PRESTO, Japan Science and Technology Agency, Kawaguchi, Japan
3M&D Data Science Center, Tokyo Medical and Dental University, Tokyo, Japan
<EMAIL_ADDRESS>
###### Abstract

Let $\Sigma$ and $\Pi$ be disjoint alphabets, respectively called the static
alphabet and the parameterized alphabet. Two strings $x$ and $y$ over
$\Sigma\cup\Pi$ of equal length are said to _parameterized match_ (_p-match_)
if there exists a renaming bijection $f$ on $\Sigma$ and $\Pi$ which is
identity on $\Sigma$ and maps the characters of $x$ to those of $y$ so that
the two strings become identical. The indexing version of the problem of
finding p-matching occurrences of a given pattern in the text is a well-
studied topic in string matching. In this paper, we present a state-of-the-art
indexing structure for p-matching called the _parameterized suffix tray_ of an
input text $T$, denoted by $\mathsf{PSTray}(T)$. We show that
$\mathsf{PSTray}(T)$ occupies $O(n)$ space and supports pattern matching
queries in $O(m+\log(\sigma+\pi)+\mathit{occ})$ time, where $n$ is the length
of $t$, $m$ is the length of a query pattern $P$, $\pi$ is the number of
distinct symbols of $|\Pi|$ in $T$, $\sigma$ is the number of distinct symbols
of $|\Sigma|$ in $T$ and $\mathit{occ}$ is the number of p-matching
occurrences of $P$ in $T$. We also present how to build $\mathsf{PSTray}(T)$
in $O(n)$ time from the parameterized suffix tree of $T$.

##  1 Introduction

_Parameterized Pattern Matching_ (PPM), first introduced by Baker [3] in
1990’s, is a well-studied class of pattern matching motivated by plagiarism
detection, software maintenance, and RNA structural matching [3, 24, 20].

PPM is defined as follows: Let $\Sigma$ and $\Pi$ be disjoint alphabets. Two
equal-length strings $x$ and $y$ from $\Sigma\cup\Pi$ are said to
parameterized match (p-match) if $x$ can be transformed to $y$ by applying a
bijection which renames the elements of $\Pi$ in $x$ (the elements of $\Sigma$
in $x$ must remain unchanged). PPM is to report every substring in a text $T$
that p-matches a pattern $P$.

In particular, the indexing version of PPM, where the task is to preprocess an
input text string $T$ so that parameterized occurrences of $P$ in $T$ can be
reported quickly, has attracted much attention for more than two decades since
the seminal paper by Baker [3].

Basically, the existing indexing structures for p-matching are designed upon
indexing structure for exact pattern matching. Namely, _parameterized suffix
trees_ [3], _parameterized suffix arrays_ [8], _parameterized DAWGs_ [21],
_parameterized CDAWGs_ [21], _parameterized position heaps_ [18, 11], and
_parameterized BWTs_ [14] are based on their exact matching counterparts:
suffix trees [25], suffix arrays [19], DAWGs [4], CDAWGs [5], position heaps
[18, 9], and BWTs [6], respectively. It should be emphasized that extending
exact-matching indexing structures to parameterized matching is not
straightforward and poses algorithmic challenges. Let $n$, $m$, $\pi$ and
$\sigma$ be the lengths of a text $T$, a pattern $P$, the number of distinct
symbols of $|\Pi|$ that appear in $T$ and the number of distinct symbols of
$|\Sigma|$ that appear in $T$, respectively. While there exist a number of
algorithms which construct the suffix array for $T$ in $O(n)$ time in the case
of integer alphabets of polynomial size in $n$ [10, 15, 17, 16, 22, 1], the
best known algorithms build the parameterized suffix array for $T$ (denoted
$\mathsf{PSA}(T)$) in $O(n\log(\sigma+\pi))$ time via the suffix tree [3, 24],
or directly in $O(n\pi)$ time [12]. The existence of a pure linear-time
algorithm for building $\mathsf{PSA}(T)$ and the parameterized suffix tree
(denoted $\mathsf{PSTree}(T)$) in the case of integer alphabets remains open.

PPM queries can be supported in $O(m+\log n+\mathit{occ})$ time by
$\mathsf{PSA}(T)$ coupled with the parameterized LCP array (denoted
$\mathsf{PLCP}(T)$) [8], or in $O(m\log(\sigma+\pi)+\mathit{occ})$ time by
$\mathsf{PSTree}(T)$ [3], where $\mathit{occ}$ is the number of occurrences to
report.

In this paper, we propose a new indexing structure for p-matching, the
_parameterized suffix tray_ for $T$ (denoted $\mathsf{PSTray}(T)$).
$\mathsf{PSTray}(T)$ is a combination of $\mathsf{PSTree}(T)$ and
$\mathsf{PSA}(T)$ and is an analogue to the _suffix tray_ indexing structure
for exact matching [7]. We show that our $\mathsf{PSTray}(T)$

  * (1)

occupies $O(n)$ space,

  * (2)

supports PPM queries in $O(m+\log(\sigma+\pi)+\mathit{occ})$, and

  * (3)

can be constructed in $O(n)$ time from $\mathsf{PSTree}(T)$ and
$\mathsf{PSA}(T)$.

Result (3) implies that $\mathsf{PSTray}(T)$ can be constructed in
$O(n\min\\{\log(\sigma+\pi),\pi\\})$ time using $O(n)$ working space [3, 24,
12]. Results (1) and (2) together with this imply that our
$\mathsf{PSTray}(T)$ is the fastest linear-space indexing structure for PPM
which can be built in time linear in $n$.

We emphasize that extending suffix trays for exact matching [7] to
parameterized matching is also not straightforward. The suffix tray of a
string $T\in\Sigma^{*}$ is a hybrid data structure of the suffix tree and
suffix array of $T$, designed as follows: Each of the $O(\frac{n}{\sigma})$
carefully-selected nodes of the suffix tree stores an array of fixed size
$\sigma$, so that pattern traversals within these selected nodes take $O(m)$
time (this also ensures a total space to be
$O(\frac{n}{\sigma}\times\sigma)=O(n)$). Once the pattern traversal reaches an
unselected node, then the search switches to the sub-array of the suffix array
of size $O(\sigma)$. This ensures a worst-case
$O(m+\log\sigma+\mathit{occ})$-time pattern matching with the suffix tray.

Now, recall that the previous-encoded suffixes of $T$ are sequences over an
alphabet $\Sigma\cup\\{0,\ldots,n-1\\}$ of size $\Theta(\sigma+n)\subseteq
O(n)$, while the alphabet size of $T$ is $\sigma+\pi$. This means that naïve
extensions of suffix trays to PPM would only result in either super-linear
$O(\frac{n^{2}}{\sigma+\pi})$ space, or $O(m+\log n+\mathit{occ})$ query time
which can be achieved already with the parameterized suffix array. We overcome
this difficulty by using the _smallest parameterized encoding_ (_spe_) of
strings which was previously proposed by the authors in the context of PPM on
labeled trees [13], and this leads to our $O(n)$-space parameterized suffix
trays with desired $O(m+\log(\sigma+\pi)+\mathit{occ})$ query time.

##  2 Preliminaries

Let $\Sigma$ and $\Pi$ be disjoint ordered sets of characters, respectively
called the static alphabet and the parameterized alphabet. We assume that any
character in $\Pi$ is lexicographically smaller than any character in
$\Sigma$. An element of $(\Sigma\cup\Pi)^{*}$ is called a _p-string_. For a
(p-)string $w=xyz$, $x$, $y$ and $z$ are called a _prefix_ , _substring_ , and
_suffix_ of $w$. The $i$-th character of a (p-)string $w$ is denoted by $w[i]$
for $1\leq i\leq|w|$, and the substring of a (p-)string $w$ that begins at
position $i$ and ends at position $j$ is denoted by $w[i:j]$ for $1\leq i\leq
j\leq|w|$. For convenience, let $w[i:j]=\varepsilon$ if $j<i$. Also, let
$w[i:]=w[i:|w|]$ for any $1\leq i\leq|w|$, and $w[:j]=w[1:j]$ for any $1\leq
j\leq|w|$. For any (p-)string $w$, let $w^{R}$ denote the reversed string of
$w$. If a p-string $x$ is lexicographically smaller than a p-string $y$, then
we write $x<y$.

######  Definition 1 (Parameterized match [2]).

Two p-strings $x$ and $y$ of the same length are said to _parameterized match_
(_p-match_) iff there is a bijection $f$ on $\Sigma\cup\Pi$ such that $f(c)=c$
for any $c\in\Sigma$ and $x[i]=f(y[i])$ for any $1\leq i\leq|x|$.

We write $x\approx y$ iff two p-strings $x,y$ p-match. For instance, if
$\Sigma=\\{\mathtt{A},\mathtt{B}\\}$,
$\Pi=\\{\mathtt{x},\mathtt{y},\mathtt{z}\\}$, then $X=\mathtt{xyzAxxxByzz}$
and $Y=\mathtt{zxyAzzzBxyy}$ p-match since there is a bijection $f$ such that
$f(\mathtt{A})=\mathtt{A}$, $f(\mathtt{B})=\mathtt{B}$,
$f(\mathtt{x})=\mathtt{z}$, $f(\mathtt{y})=\mathtt{x}$,
$f(\mathtt{z})=\mathtt{y}$, and

$f(\mathtt{x})f(\mathtt{y})f(\mathtt{z})f(\mathtt{A})f(\mathtt{x})f(\mathtt{x})f(\mathtt{x})f(\mathtt{B})f(\mathtt{y})f(\mathtt{z})f(\mathtt{z})=\mathtt{zxyAzzzBxyy}=Y.$

######  Definition 2 (Parameterized Pattern Matching problem(PPM) [2]).

Given a text p-string $T$ and a pattern p-string $P$, find all positions $i$
in $T$ such that $T[i:i+|P|-1]\approx p$.

For instance, if $\Sigma=\\{\mathtt{A}\\}$, $\Pi=\\{\mathtt{x},\mathtt{y}$,
$\mathtt{z}\\}$, $T=\mathtt{xyzAxxxAyyzAzx}$, and $P=\mathtt{yAzz}$, then the
out put for PPM is $\\{3,7\\}$. We call the positions in the output of PPM the
_p-beginning positions_ for given text $T$ and pattern $P$. We say that the
pattern _p-appears_ in the text $T$ iff the pattern and a substring of the
text p-match. In this paper, we suppose that a given text $T$ terminates with
a special end-marker $\$$ which occurs nowhere else in $T$. We assume that
$\$$ is an element of $\Sigma$ and $\$$ is lexicographically larger than any
elements from $\Sigma$ and $\Pi$.

######  Definition 3 (Previous encoding [2]).

For a p-string $w$, the previous encoding $\mathsf{prev}(w)$ is a string of
length $|w|$ such that for each $1\leq i\leq|w|$,

$\mathsf{prev}(w)[i]=\begin{cases}w[i]&\mbox{if $w[i]\in\Sigma$},\\\
0&\mbox{if $w[i]\in\Pi$ and $w[j]\neq w[i]$ for any $1\leq j<i$},\\\
i-j&\mbox{otherwise, $w[i]=w[j]$ and $w[i]\neq w[k]$ for any
$j<k<i$}.\end{cases}$

Intuitively, when we transform $w$ to $\mathsf{prev}(w)$, the first occurrence
of each element of $\Pi$ is replaced with 0 and any other occurrence of the
element of $\Pi$ is replaced by the distance to the previous occurrence of the
same character, and each element of $\Sigma$ remains the same.

######  Definition 4 (Smallest parameterized encoding (spe) [13]).

For a p-string $w$, the smallest parameterized encoding $\mathsf{spe}(w)$ is
the lexicographically smallest p-string such that $w\approx\mathsf{spe}(w)$.

Namely, $\mathsf{spe}(w)$ maps a given string $w$ to the representative of the
equivalence class of p-strings under p-matching $\approx$.

For any two p-strings $w_{1},w_{2}$,
$\mathsf{prev}(w_{1})=\mathsf{prev}(w_{2})\Leftrightarrow\mathsf{spe}(w_{1})=\mathsf{spe}(w_{2})\Leftrightarrow
w_{1}\approx w_{2}$. For instance, let $\Sigma=\\{\mathtt{A,B}\\}$,
$\Pi=\\{\mathtt{x},\mathtt{y},\mathtt{z}\\}$, $X=\mathtt{yxzAyyyBxzz}$, and
$Y=\mathtt{zxyAzzzBxyy}$. Then
$\mathsf{prev}(X)=\mathtt{000A411B771}=\mathsf{prev}(Y)$ and
$\mathsf{spe}(X)=\mathtt{xyzAxxxByzz}=\mathsf{spe}(Y)$.

##  3 Parameterized suffix trays

In this section, we propose a new indexing structure called the _parameterized
suffix tray_ for PPM, and we discuss its space requirements.

Our parameterized suffix trays are a “hybrid” data structure of parameterized
suffix trees and parameterized suffix arrays, which are defined as follows:

######  Definition 5 (Parameterized suffix trees [3]).

The _parameterized suffix tree_ for a p-string $T$, denoted
$\mathsf{PSTree}(T)$, is a compact trie that stores the set
$\\{\mathsf{prev}(T[i:])\mid 1\leq i\leq|T|\\}$ of the previous encodings of
all suffixes of $T$.

See Figure 1 for examples of $\mathsf{PSTree}(T)$. We assume that the leaves
of $\mathsf{PSTree}(T)$ are sorted in lexicographical order, so that the
sequence of the leaves corresponds to the parameterized suffix array for $T$,
which is defined below.

Figure 1: $\mathsf{PSTree}(T)$ for a p-string $T=\mathtt{zAxAyyxyAxxy}$, where
$\Sigma=\\{\mathtt{A},\mathtt{\$}\\},\Pi=\\{\mathtt{x},\mathtt{y},\mathtt{z}\\}$.

######  Definition 6 (Parameterized suffix arrays [8]).

The _parameterized suffix array_ of a p-string $T$, denoted $\mathsf{PSA}(T)$,
is an array of integers such that $\mathsf{PSA}(T)[i]=j$ if and only if
$\mathsf{prev}(T[j:])$ is the $i$th lexicographically smallest string in
$\\{\mathsf{prev}(T[i:])\ |\ 1\leq i\leq|T|\\}$.

######  Definition 7 (Parameterized longest common prefix arrays [8]).

The parameterized longest common prefix array of a p-string $T$, denoted
$\mathsf{PLCP}(T)$, is an array of integers such that $\mathsf{PLCP}(T)[1]=0$
and $2\leq i\leq|T|$ $\mathsf{PLCP}(T)[i]$ stores the length of the longest
common prefix between $\mathsf{prev}(T[\mathsf{PSA}(T)[i-1]:])$ and
$\mathsf{prev}(T[\mathsf{PSA}(T)[i]:])$.

See Figure 2 for examples of $\mathsf{PSA}(T)$ and $\mathsf{PLCP}(T)$.

$i$ | $\mathsf{PSA}(T)[i]$ | $T[\mathsf{PSA}(T)[i]:]$ | $\mathsf{PLCP}(i)$
---|---|---|---
1 | 6 | 0 0 2 $\mathtt{A}$ 3 1 4 $ | 0
2 | 7 | 0 0 $\mathtt{A}$ 3 1 4 $ | 2
3 | 11 | 0 0 $ | 2
4 | 5 | 0 1 0 2 $\mathtt{A}$ 3 1 4 $ | 1
5 | 10 | 0 1 0 $ | 3
6 | 3 | 0 $\mathtt{A}$ 0 1 4 2 $\mathtt{A}$ 3 1 4 $ | 1
7 | 8 | 0 $\mathtt{A}$ 0 1 4 $ | 5
8 | 1 | 0 $\mathtt{A}$ 0 $\mathtt{A}$ 0 1 4 2 $\mathtt{A}$ 3 1 4 $ | 3
9 | 12 | 0 $ | 1
10 | 4 |  $\mathtt{A}$ 0 1 0 2 $\mathtt{A}$ 3 1 4 $ | 0
11 | 9 |  $\mathtt{A}$ 0 1 0 $ | 4
12 | 2 |  $\mathtt{A}$ 0 $\mathtt{A}$ 0 1 4 2 $\mathtt{A}$ 3 1 4 $ | 2
13 | 13 | $ | 0
Figure 2: $\mathsf{PSA}(T)$ and $\mathsf{PLCP}(T)$ for a p-string
$T=\mathtt{zAxAyyxyAxxy}$, where
$\Sigma=\\{\mathtt{A},\mathtt{\$}\\},\Pi=\\{\mathtt{x},\mathtt{y},\mathtt{z}\\}$.

In addition to the above data structures from the literature, we introduce the
following new notions and data structures. For convenience, we will sometimes
identify each node of the parameterized suffix tree with the string which is
represented by that node.

In what follows, let $\Pi_{T}=\\{T[i]\in\Pi\mid 1\leq i\leq|T|\\}$ and
$\Sigma_{T}=\\{T[i]\in\Sigma\mid 1\leq i\leq|T|\\}$, namely, $\Pi_{T}$ (resp.
$\Sigma_{T}$) is the set of distinct characters of $\Pi$ (resp. $\Sigma$) that
occur in $T$. Let $\pi=|\Pi_{T}|$ and $\sigma=|\Sigma_{T}|$.

######  Definition 8 (P-nodes, branching p-nodes).

Let $T$ be a p-string over $\Sigma\cup\Pi$. A node $v$ in $\mathsf{PSTree}(T)$
is called a _p-node_ if the number of leaves in the subtree of
$\mathsf{PSTree}(T)$ rooted at $v$ is at least $\max\\{\sigma,\pi\\}$. A
p-node $v$ is called a _branching p-node_ if at least two children of $v$ in
$\mathsf{PSTree}(T)$ are p-nodes.

See Figure 3 for examples of p-nodes and branching p-nodes.

Figure 3: $\mathsf{PSTree}(T)$ for a p-string $T=\mathtt{zAxAyyxyAxxy}$, where
$\Sigma=\\{\mathtt{A},\mathtt{\$}\\},\Pi=\\{\mathtt{x},\mathtt{y},\mathtt{z}\\}$.Then
black nodes are p-nodes because the number of leaves in the subtree of
$\mathsf{PSTree}(T)$ rooted at them are at least $\max\\{\sigma,\pi\\}=3$.
Checked nodes are branching p-nodes because at least two children of them in
$\mathsf{PSTree}(T)$ are p-nodes.

For any $x\in\Pi_{T}$, let $\mathsf{rank}_{T}(x)$ denote the lexicographical
rank of $x$ in $\Pi_{T}\cup\Sigma_{T}$. Assuming that $\Pi$ and $\Sigma$ are
integer alphabets of polynomial size in $n$, we can compute
$\mathsf{rank}_{T}(x)$ for every $x\in\Pi_{T}$ in $O(n)$ time by bucket sort.
We will abbreviate $\mathsf{rank}_{T}(x)$ as $\mathsf{rank}(x)$ when it is not
confusing.

######  Definition 9 (P-array).

Let $\mathsf{prev}(v)$ be any branching p-node of $\mathsf{PSTree}(T)$, where
$v$ is some substring of $T$. The _p-array_ $A(\mathsf{prev}(v))$ for
$\mathsf{prev}(v)$ is an array of length $\sigma+\pi$ such that for each
$x\in\Sigma\cup\Pi$, $A(\mathsf{prev}(v))[\mathsf{rank}(x)]$ stores a pointer
to the child $u$ of $\mathsf{prev}(v)$ such that
$\mathsf{prev}(\mathsf{spe}(v)x)$ is a prefix of $u$ if such a child exists,
and $A(\mathsf{prev}(v))[\mathsf{rank}(x)]$ stores nil otherwise.

See Figure 4 for an example of a p-array.

Figure 4: $\mathsf{PSTree}(T)$ for a p-string $T=\mathtt{zAxAyyxyAxxy}$, where
$\Sigma_{T}=\\{\mathtt{A},\mathtt{\$}\\},\Pi_{T}=\\{\mathtt{x},\mathtt{y},\mathtt{z}\\}$.
Consider a branching p-node $\mathsf{prev}(v)=\mathtt{0A0}$ where $v$ is e.g.
$\mathtt{zAx}$. Then,
$A(\mathtt{0A0})[\mathsf{rank}(\mathtt{y})]=A(\mathtt{0A0})[2]$ stores a
pointer to node $\mathtt{0A014}$ because $\mathsf{spe}(v)=\mathtt{xAy}$ and
$\mathsf{prev}(\mathsf{spe}(v)\mathtt{y}=\mathtt{xAyy})=\mathtt{0A01}$ is a
prefix of node $\mathtt{0A014}$.

######  Definition 10 (Parameterized suffix tray).

The parameterized suffix tray of a p-string $T$, denoted $\mathsf{PSTray}(T)$,
is a hybrid data structure consisting of $\mathsf{PSA}(T)$,
$\mathsf{PLCP}(T)$, and $\mathsf{PSTree}(T)$ where each branching p-node is
augmented with the p-array.

We can show the following lemmas regarding the space requirements of
$\mathsf{PSTray}(T)$, by similar arguments to [7] for suffix trays on standard
strings.

######  Lemma 1.

For any p-string $T$ of length $n$ over $\Sigma\cup\Pi$, the number of
branching p-nodes in $\mathsf{PSTree}(T)$ is $O(\frac{n}{\pi+\sigma})$.

######  Lemma 2.

For any p-string $T$ of length $n$, $\mathsf{PSTray}(T)$ occupies $O(n)$
space.

##  4 PPM using parameterized suffix trays

In this section, we present our algorithm for parameterized pattern matching
(PPM) on $\mathsf{PSTray}(T)$. For any node $v$ in $\mathsf{PSTray}(T)$, let
$l_{v}=(i,j)$ denote the range of $\mathsf{PSA}(T)$ that $v$ corresponds,
namely, $l_{v}=(i,j)$ iff the leftmost and rightmost leaves in the subtree
rooted at $v$ correspond to the $i$th and $j$th entries of $\mathsf{PSA}(T)$,
respectively. For any _p-node_ $v$, we store $l_{v}$ in $v$. Also, for any
_non-branching_ p-node $u$, we store a pointer to the unique child of $u$ that
is a p-node. These can be easily computed in a total of $O(n)$ time by a
standard traversal on $\mathsf{PSTree}(T)$.

The basic strategy for PPM with $\mathsf{PSTray}(T)$ follows the (exact)
pattern matching algorithm with suffix trays on standard strings [7]. Namely,
we traverse $\mathsf{PSTree}(T)$ with a given pattern $P$ from the root, and
as soon as we encounter a node that is not a p-node, then we switch to the
corresponding range of $\mathsf{PSA}(T)$ and perform a binary search to locate
the pattern occurrences. The details follow.

Let $P$ be a pattern p-string of length $m$. We assume that $\Pi$ and $\Sigma$
are disjoint integer alphabets, where $\Pi=\\{0,\ldots,c_{1}n\\}$ and
$\Sigma=\\{c_{1}n+1,\ldots,n^{c_{2}}\\}$ for some positive constants $c_{1}$
and $c_{2}$. Using an array (bucket) $B$ of size $|\Pi|=c_{1}n\in O(n)$, we
can compute $\mathsf{prev}(P)$ in $O(m)$ time by scanning $P$ from left to
right and keeping the last occurrence of each character $x\in\Pi$ in $P$ in
$B[x]$. We can compute $\mathsf{spe}(P)$ in $O(m)$ time in a similar manner
with a bucket. These buckets are a part of our indexing structure that
occupies $O(n)$ total space.

After computing $\mathsf{prev}(P)$ and $\mathsf{spe}(P)$, we traverse
$\mathsf{prev}(P)$ on $\mathsf{PSTray}(T)$. If $\mathsf{prev}(P[:i])$ for
prefix $P[:i]$ ($1\leq i\leq m$) is represented by a p-node, we can find the
out-going edge whose label begins with $\mathsf{prev}(P)[i+1]$ in constant
time by accessing the p-array entry
$A(\mathsf{prev}(P[:i]))[\mathsf{spe}(P)[i+1]]$. Therefore, we can solve PPM
in $O(m+\mathit{occ})$ time if $\mathsf{prev}(P)$ is a prefix of some p-node
in $\mathsf{PSTray}(T)$. Otherwise (if $\mathsf{prev}(P)$ is not a prefix of
any p-node), there exists integer $i$ such that $\mathsf{prev}(P[:i])$ is not
a p-node but the parent of $\mathsf{prev}(P[:i])$ is a p-node. In this case,
we will use the next lemma.

######  Lemma 3 (PPM in PSA range (adapted from [8])).

Given a pattern p-string $P$ of length $m$ and a range $[j,k]$ in
$\mathsf{PSA}(T)$ such that the $\mathit{occ}$ occurrences of $P$ in $T$ lie
in the range $[j,k]$ of $\mathsf{PSA}(T)$, we can find them in
$O(m+\log(k-j)+\mathit{occ})$ time by using $\mathsf{PSA}(T)$ and
$\mathsf{PLCP}(T)$.

Let $I_{\mathsf{prev}(P[:i])}=(j,k)$ denote the range in $\mathsf{PSA}(T)$
where $\mathsf{prev}(P)$ is a prefix of the suffixes in the range. We apply
Lemma 3 to this range so we can find the parameterized occurrences of $P$ in
$T$ in $O(m+\log(k-j)+\mathit{occ})$ time. By Definition 8 we have
$k-j\leq\pi+\sigma$ (recall that $\mathsf{prev}(P[:i])$ is not a p-node).
Thus, $O(m+\log(k-j)+\mathit{occ})\subseteq
O(m+\log(\pi+\sigma)+\mathit{occ})$, implying the next theorem.

######  Theorem 1.

Suppose $|\Pi|=O(n)$. Then, $\mathsf{PSTray}(T)$ supports PPM queries in
$O(m+\log(\pi+\sigma)+\mathit{occ})$ time each, where $m$ is the length of a
query pattern $P$ and $\mathit{occ}$ is the number of occurrences to report.

##  5 Construction of parameterized suffix trays

Let $T$ be a p-string of length $n$. In this section, we show how to construct
$\mathsf{PSTray}(T)$ provided that $\mathsf{PSTree}(T)$ has already been
built. Throughout this section we assume that $\Pi$ and $\Sigma$ are disjoint
integer alphabets, both being of polynomial size in $n$, namely,
$\Pi=\\{0,...,n^{c_{1}}\\}$ and $\Sigma=\\{n^{c_{1}}+1,...,n^{c_{2}}\\}$ for
some positive constants $c_{1}$ and $c_{2}$. For convenience, we define the
following two notions.

######  Definition 11 (P-function).

Let $q,r$ be p-strings such that $q\approx r$. The _p-function_
$\mathsf{f}_{q,r}:\Sigma\cup\Pi\rightarrow\Sigma\cup\Pi$ transforms $q$ to
$r$, namely, for every $1\leq i\leq h$

$\mathsf{f}_{q,r}(q[i])=r[i].$

For instance, if $\Pi=\\{\mathtt{x},\mathtt{y},\mathtt{z}\\}$,
$q=\mathtt{xyxzyyxz}$, $r=\mathtt{zxzyxxzy}$ and $q\approx r$, then
$\mathsf{f}_{q,r}(\mathtt{x})=\mathtt{z}$,
$\mathsf{f}_{q,r}(\mathtt{y})=\mathtt{x}$,
$\mathsf{f}_{q,r}(\mathtt{z})=\mathtt{y}$ since $q$ can be transformed $r$ by
this function.

######  Definition 12 (F-array).

Let $q$ be a p-string and $x\in\Pi_{T}$. The first (left-most) occurrence of
$x$ in $q$ is denoted by $i_{q,x}$. The _f-array_ of $q$, denoted
$\mathsf{fpos}(q)$, is an array of length $\pi$ such that
$\mathsf{fpos}(q)[\mathsf{rank}(x)]=i_{q,x}$.

For instance, if $\Pi_{T}=\\{\mathtt{x},\mathtt{y},\mathtt{z}\\}$ and
$q=\mathtt{xyxzyyxz}$, then
$\mathsf{fpos}(q)[\mathsf{rank}(\mathtt{x})]=\mathsf{fpos}(q)[1]=1$,
$\mathsf{fpos}(q)[\mathsf{rank}(\mathtt{y})]=\mathsf{fpos}(q)[2]=2$, and
$\mathsf{fpos}(q)[\mathsf{rank}(\mathtt{z})]=\mathsf{fpos}(q)[3]\\\ =4$.

Given $\mathsf{PSTree}(T)$, we show how to construct $\mathsf{PSTray}(T)$. It
is well known that $\mathsf{PSA}(T)$ and $\mathsf{PLCP}(T)$ can be constructed
from $\mathsf{PSTree}(T)$ in $O(n)$ time. In the following, we consider how to
compute $A(\mathsf{prev}(v))$ for every p-node $\mathsf{prev}(v)$ in
$\mathsf{PSTree}(T)$.

First, we consider how to compute (branching) p-nodes in $\mathsf{PSTree}(T)$.
This can be done by a similar method to the suffix tray for exact matching
[7], namely:

######  Lemma 4 (Computing p-node).

We can compute all p-nodes and branching p-nodes in $\mathsf{PSTree}(T)$ in
$O(n)$ total time.

Our algorithm performs a bottom-up traversal on $\mathsf{PSTree}(T)$ and
propagates pairs $(\mathsf{fpos}(T[i:]),i)$ from leaves to their ancestors.
Each internal p-node $\mathsf{prev}(v)$ will store only a single pair
$(\mathsf{fpos}(T[i:]),i)$, where $i$ is the largest position in $T$ such that
$\mathsf{prev}(T[i:])$ is a leaf in the subtree rooted at $\mathsf{prev}(v)$
111Indeed, our $\mathsf{PSTray}(T)$ construction algorithm works with any
position $i$ in the subtree rooted at $\mathsf{prev}(v)$, and we propagate the
largest leaf position $i$ to each internal p-node for simplicity.. See also
Figure 5. One can easily compute the pairs for all p-nodes in a total of
$O(n)$ time.

Figure 5: $\mathsf{PSTree}(T)$ for a p-string $T=\mathtt{zAxAyyxyAxxy}$, where
$\Sigma=\\{\mathtt{A},\mathtt{\$}\\}$ and
$\Pi=\\{\mathtt{x},\mathtt{y},\mathtt{z}\\}$. For instance, we propagate
$\mathsf{fpos}(T[12:])$ (coupled with the corresponding position $12$) to the
p-node $\mathtt{0}$.

Then, we compute $\mathsf{f}_{v,\mathsf{spe}(v)}$ for every p-node
$\mathsf{prev}(v)$ from the pair $(\mathsf{fpos}(T[i:]),i)$ that is stored in
the p-node $\mathsf{prev}(v)$. Finally, for every p-node $\mathsf{prev}(v)$ we
compute $A_{\mathsf{prev}(v)}$ from $\mathsf{f}_{v,\mathsf{spe}(v)}$ and $i$.

In what follows, we first show how to compute $A_{\mathsf{prev}(v)}$ from
$\mathsf{f}_{v,\mathsf{spe}(v)}$ and $i$ in Lemmas 5 and 6. We then present
how to compute $\mathsf{f}_{v,\mathsf{spe}(v)}$ and $i$ from
$\mathsf{fpos}(T[i:])$ in Lemma 7, and how to compute $\mathsf{fpos}(T[i:])$
in Lemma 8. These lemmas will ensure the correctness and time complexity of
our algorithm.

We consider how to compute $A(\mathsf{prev}(v))$ for a given p-node
$\mathsf{prev}(v)$.

######  Lemma 5.

Let $s$ be a p-string. If $\mathsf{prev}(s)[|s|]=k\in\\{0,\ldots,|T|-1\\}$,
then $\mathsf{spe}(s)[|s|]=\mathsf{spe}(s)[|s|-k]$.

###### Proof.

Clear from the definitions of $\mathsf{prev}(\cdot)$ and
$\mathsf{spe}(\cdot)$. ∎

In the sequel, let $\mathsf{prev}(T[i:])$ be any leaf in the subtree rooted at
$\mathsf{prev}(v)$, where $1\leq i\leq|T|$. By Lemma 5, we can compute
$A(\mathsf{prev}(v))$ if we know $\mathsf{spe}(v)[|v|-k+1]$, where
$k=\mathsf{prev}(T[i:])[|v|+1]$.

######  Lemma 6.

$\mathsf{spe}(v)[|v|-k+1]=\mathsf{f}_{T[i:i+|v|-1],\mathsf{spe}(T[i:i+|v|-1])T[i+|v|+k-2]}$.

###### Proof.

Clear from the definitions of $\mathsf{f}_{\cdot,\cdot}$ and
$\mathsf{spe}(\cdot)$. ∎

We can compute $\mathsf{spe}(v)[|v|-k+1]$ if we know
$\mathsf{f}_{T[i:i+|v|-1],\mathsf{spe}(v)}$. In the next lemma, we show how to
compute $\mathsf{f}_{T[i:i+|v|-1],\mathsf{spe}(v)}$ for all p-nodes
$\mathsf{prev}(v)$.

######  Lemma 7.

For every p-node $\mathsf{prev}(v)$, we can compute
$\mathsf{f}_{T[i:i+|v|-1],\mathsf{spe}(T[i:i+|v|-1])}$ with
$\mathsf{prev}(v)=\mathsf{prev}(T[i:i+|v|-1]))$ in amortized $O(\pi)$ time if
we know pair $\mathsf{fpos}(T[i:],i)$.

###### Proof.

Let $x_{j}$ be the $j$th smallest element of $\Pi$ in lexicographically order.
Let $y_{l}$ denote the parameterized character in $S=T[i:i+|v|-1]$ such that
if $j$ is the left-most occurrence of $y_{l}$ in $S$ (i.e. $j=\min\\{h\mid
S[h]=y_{l}\\}$), then $|\Pi_{S[1..j]}|=l$. For instance, for
$S=\mathtt{xAzAyA}$, then $y_{1}=\mathtt{x}$, $y_{2}=\mathtt{z}$, and
$y_{3}=\mathtt{y}$. Let
$(i_{\mathsf{prev}(v)},\mathsf{fpos}(T[i_{\mathsf{prev}(v)}:])$ denote the
pair stored in p-node $\mathsf{prev}(v)$. Consider a set
$\mathbf{I}=\\{(i_{\mathsf{prev}(v)},\mathsf{fpos}(T[i_{\mathsf{prev}(v)}:])[k])\mid\text{$\mathsf{prev}(v)$
is a p-node},1\leq k\leq\pi\\}$ of integer pairs. We sort the elements of
$\mathbf{I}$ so that we can compute in $O(1)$ time
$\mathsf{f}_{T[i:i+|v|-1],\mathsf{spe}(v)}(y_{l})=x_{l}$ for all p-nodes
$\mathsf{prev}(v)$, where $x_{l}$ is the $l$th smallest parameterized
character that occurs in $\mathsf{spe}(v)$. We can sort the elements of
$\mathbf{I}$ in a total of $O(n)$ time by radix sort, since there are
$O(\frac{n}{\sigma+\pi})$ p-nodes and each f-array $\mathsf{fpos}(T[i:])$ is
of length $\pi$. This completes the proof. ∎

We can easily compute $\mathsf{fpos}(T[i:])$ by the following lemma:

######  Lemma 8.

Let $q$ be a p-string. Let $x\in\Pi$, $y\in\Pi\cup\Sigma$ and $x\neq y$. Then
the following equations hold:

$\displaystyle\mathsf{fpos}(xq)[\mathsf{rank}(x)]$ $\displaystyle=$
$\displaystyle 1,$ $\displaystyle\mathsf{fpos}(xq)[\mathsf{rank}(y)]$
$\displaystyle=$ $\displaystyle\mathsf{fpos}(q)[\mathsf{rank}(y)]+1.$

Thus we can compute f-arrays $\mathsf{fpos}(T[i:])$ for all $1\leq i\leq n$ in
a total of $O(n)$ time.

Since all the afore-mentioned procedures take $O(n)$ time each, we obtain the
main theorem of this section.

######  Theorem 2.

Given a p-string $T$ of length $n$ over alphabet $\Sigma\cup\Pi$ with
$\Pi=\\{0,...,n^{c_{1}}\\}$ and $\Sigma=\\{n^{c_{1}}+1,...,n^{c_{2}}\\}$ for
some positive constants $c_{1}$ and $c_{2}$, we can construct
$\mathsf{PSTray}(T)$ in $O(n)$ time from $\mathsf{PSTree}(T)$.

##  6 Conclusions and open questions

In this paper, we proposed an indexing structure for parameterized pattern
matching (PPM) called the parameterized suffix tray $\mathsf{PSTray}(T)$,
where $T$ is a given text string. Our $\mathsf{PSTray}(T)$ uses $O(n)$ space
and supports pattern matching queries in $O(m+\log(\sigma+\pi)+\mathit{occ})$
time, where $n=|T|$, $m$ is the query pattern length, $\sigma$ and $\pi$ are
respectively the numbers of distinct static characters and distinct
parameterized characters occurring in $T$, and $\mathit{occ}$ is the number of
pattern occurrences to report. We also showed how to construct
$\mathsf{PSTray}(T)$ in $O(n+s(n))$ time, where $s(n)$ denotes the time
complexity to build the parameterized suffix tree $\mathsf{PSTree}(T)$ for
$T$. It is known that $s(n)=\min\\{n\pi,n(\log(\pi+\sigma)\\}$ [3, 24, 12].

On the other hand, if we use hashing for implementing the branches of the
parameterized suffix tree $\mathsf{PSTree}(T)$, one can trivially answer PPM
queries in $O(m+\mathit{occ})$ time with $O(n)$ space. The best linear-space
deterministic hashing we are aware of is the one by Ružić [23], which can be
built in $O(n(\log\log n)^{2})$ time for a set of $n$ keys in the word RAM
model with machine word size $\Omega(\log n)$. By associating each node of
$\mathsf{PSTree}(T)$ with a unique integer (e.g. the pre-order rank), one can
regard each branch in $\mathsf{PSTree}(T)$ as an integer from the universe of
polynomial size in $n$, each fitting in a constant number of machine words.
This gives us a deterministic $O(n(\log\log n)^{2}+s(n))$-time algorithm for
building $\mathsf{PSTree}(T)$ with $O(m+\mathit{occ})$-time PPM queries.
Still, it is not known whether a similar data structure can be build in
$O(n+s(n))$ time. We conjecture that our $O(m+\log(\sigma+\pi)+\mathit{occ})$
PPM query time would be the best possible for any indexing structure that can
be build in $O(n+s(n))$ time. Proving or disproving such a lower bound is an
intriguing open problem.

## Acknowledgments

This work was supported by JSPS KAKENHI Grant Numbers JP18K18002 (YN),
JP17H01697 (SI), JP20H04141 (HB), JP18H04098 (MT), and JST PRESTO Grant Number
JPMJPR1922 (SI).

## References

  * [1] U. Baier.  Linear-time suffix sorting - A new approach for suffix array construction.  In CPM 2016, pages 23:1–23:12, 2016.
  * [2] B. S. Baker.  A theory of parameterized pattern matching: algorithms and applications.  In STOC 1993, pages 71–80, 1993.
  * [3] B. S. Baker.  Parameterized pattern matching: Algorithms and applications.  J. Comput. Syst. Sci., 52(1):28–42, 1996.
  * [4] A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen, and J. Seiferas.  The smallest automaton recognizing the subwords of a text.  Theoretical Computer Science, 40:31–55, 1985.
  * [5] A. Blumer, J. Blumer, D. Haussler, R. Mcconnell, and A. Ehrenfeucht.  Complete inverted files for efficient text retrieval and analysis.  Journal of the ACM, 34(3):578–595, 1987.
  * [6] M. Burrows and D. J. Wheeler.  A block sorting lossless data compression algorithm, 1994.
  * [7] R. Cole, T. Kopelowitz, and M. Lewenstein.  Suffix trays and suffix trists: Structures for faster text indexing.  Algorithmica, 72(2):450–466, 2015.
  * [8] S. Deguchi, F. Higashijima, H. Bannai, S. Inenaga, and M. Takeda.  Parameterized suffix arrays for binary strings.  In PSC 2008, pages 84–94, 2008.
  * [9] A. Ehrenfeucht, R. M. McConnell, N. Osheim, and S.-W. Woo.  Position heaps: A simple and dynamic text indexing data structure.  Journal of Discrete Algorithms, 9(1):100–121, 2011.
  * [10] M. Farach-Colton, P. Ferragina, and S. Muthukrishnan.  On the sorting-complexity of suffix tree construction.  J. ACM, 47(6):987–1011, 2000.
  * [11] N. Fujisato, Y. Nakashima, S. Inenaga, H. Bannai, and M. Takeda.  Right-to-left online construction of parameterized position heaps.  In PSC 2018, pages 91–102, 2018.
  * [12] N. Fujisato, Y. Nakashima, S. Inenaga, H. Bannai, and M. Takeda.  Direct linear time construction of parameterized suffix and LCP arrays for constant alphabets.  In SPIRE 2019, pages 382–391, 2019.
  * [13] N. Fujisato, Y. Nakashima, S. Inenaga, H. Bannai, and M. Takeda.  The parameterized position heap of a trie.  In CIAC 2019, pages 237–248, 2019.
  * [14] A. Ganguly, R. Shah, and S. V. Thankachan.  pBWT: Achieving succinct data structures for parameterized pattern matching and related problems.  In SODA 2017, pages 397–407, 2017.
  * [15] J. Kärkkäinen, P. Sanders, and S. Burkhardt.  Linear work suffix array construction.  J. ACM, 53(6):918–936, 2006.
  * [16] D. K. Kim, J. S. Sim, H. Park, and K. Park.  Constructing suffix arrays in linear time.  J. Discrete Algorithms, 3(2-4):126–142, 2005.
  * [17] P. Ko and S. Aluru.  Space efficient linear time construction of suffix arrays.  J. Discrete Algorithms, 3(2-4):143–156, 2005.
  * [18] G. Kucherov.  On-line construction of position heaps.  J. Discrete Algorithms, 20:3–11, 2013.
  * [19] U. Manber and G. Myers.  Suffix arrays: A new method for on-line string searches.  SIAM J. Computing, 22(5):935–948, 1993.
  * [20] J. Mendivelso, S. V. Thankachan, and Y. J. Pinzón.  A brief history of parameterized matching problems.  Discret. Appl. Math., 274:103–115, 2020.
  * [21] K. Nakashima, N. Fujisato, D. Hendrian, Y. Nakashima, R. Yoshinaka, S. Inenaga, H. Bannai, A. Shinohara, and M. Takeda.  DAWGs for parameterized matching: Online construction and related indexing structures.  In CPM 2020, pages 26:1–26:14, 2020.
  * [22] G. Nong, S. Zhang, and W. H. Chan.  Two efficient algorithms for linear time suffix array construction.  IEEE Trans. Computers, 60(10):1471–1484, 2011.
  * [23] M. Ružić.  Constructing efficient dictionaries in close to sorting time.  In ICALP 2008, volume 5125 of Lecture Notes in Computer Science, pages 84–95. Springer, 2008.
  * [24] T. Shibuya.  Generalization of a suffix tree for RNA structural pattern matching.  Algorithmica, 39(1):1–19, 2004.
  * [25] P. Weiner.  Linear pattern-matching algorithms.  In Proc. of 14th IEEE Ann. Symp. on Switching and Automata Theory, pages 1–11, 1973.