text:
\section*{Acknowledgments}
The authors would like to thank the people who provided the source codes.
This work was supported by JSPS KAKENHI Grant Numbers JP17H06923, JP17H01697, JP16H02783, JP18H04098, and JP18K11149, Japan.
This work was also supported by JST CREST Grant Number JPMJCR1402, Japan.

\section{Appendix}\label{appendix}

We show Figures~\ref{fig:apprp},~\ref{fig:appnmr},~and~\ref{fig:appmr} to help for understanding Proof of Theorem~\ref{theo:naive}.

Let $\gram{rp}$, $\gram{nmr}$, and $\gram{mr}$ be the grammars generated by RePair, Na\"{\i}ve-MR-RePair, and MR-RePair, respectively.
For a given text $T = a_1\cdots a_n ~(a_i \in \Sigma, ~1\le i\le n)$ of length $|T| = n$,
let $\gsize{rp}$, $\gsize{nmr}$, and $\gsize{mr}$ be the sizes of $\gram{rp}$, $\gram{nmr}$, and $\gram{mr}$, respectively.
Here, assume that $T = (aw)^{2(2^m-1)+1} a$,
where $w\in \Sigma^{+}$ such that $awa$ is the most frequent maximal repeat of $T$,
and $m \in \mathbb{N}^{+}$.
Then, by Proof of Theorem~\ref{theo:naive}, $\gsize{nmr} > \gsize{rp}$ holds with
some $m$ and $w$ such that $(m - 1)(|w| - 1) > 1$.

We show a concrete example of the grammar generation process of RePair\xspace and $\gram{rp}$
for $T = ({\rm {\tt abcd}})^7{\rm {\tt a}}$ with $m = 2$ and $|w| = 3$ in Figure~\ref{fig:apprp}.
The size $\gsize{rp}$ is $18$ for this example.
We also show an example of the process of Na\"{\i}ve-MR-RePair\xspace and $\gram{nmr}$ for the same $T$ in Figure~\ref{fig:appnmr}.
As we see, the size $\gsize{nmr}$ is $19$, and thus $\gsize{nmr} > \gsize{rp}$ holds.
As shown in Figure~\ref{fig:appnmr}, in particular cases,
Na\"{\i}ve-MR-RePair\xspace may fail to extract repetitive patterns
(like {\tt abcd} of $({\rm {\tt abcd}})^7{\rm {\tt a}}$ for the running example).
However, this problem is solved by using MR-RePair.
We show an example of the process of MR-RePair\xspace and $\gram{mr}$ for the same $T = ({\rm {\tt abcd}})^7{\rm {\tt a}}$ in Figure~\ref{fig:appmr}.
The size $\gsize{mr}$ is $16$ and this is smaller than $\gsize{rp} = 18$.
While the most frequent maximal repeat at the second replacement step is
$v_{\rm {\tt a}}v_{\rm {\tt b}}v_{\rm {\tt c}}v_{\rm {\tt d}}v_{\rm {\tt a}}$,
MR-RePair\xspace replaces
$v_{\rm {\tt a}}v_{\rm {\tt b}}v_{\rm {\tt c}}v_{\rm {\tt d}}$ with new variable $v_1$
because of the additional {\bf Step 3} of Definition~\ref{def:mr}.

\begin{landscape}
	\begin{figure}
	\includegraphics[angle=270, trim=0cm 0cm 17cm 0cm, clip, scale=0.85]{figapprp.pdf}
		\caption{Grammar generation process of RePair\xspace and its generated grammar for text $({\rm {\tt abcd}})^{7}${\tt a}.
		The grammar size is $18$.}%
	\label{fig:apprp}
	\end{figure}

	\begin{figure}
	\includegraphics[angle=270, trim=0cm 0cm 18.2cm 0cm, clip, scale=0.85]{figappnmr.pdf}
		\caption{Grammar generation process of Na\"{\i}ve-MR-RePair\xspace and its generated grammar for text $({\rm {\tt abcd}})^{7}${\tt a}.
		The grammar size is $19$.}%
	\label{fig:appnmr}
	\end{figure}

	\begin{figure}
	\includegraphics[angle=270, trim=0cm 0cm 17.8cm 0cm, clip, scale=0.85]{figappmr.pdf}
		\caption{Grammar generation process of MR-RePair\xspace and its generated grammar for text $({\rm {\tt abcd}})^{7}${\tt a}.
		The grammar size is $16$.}%
	\label{fig:appmr}
	\end{figure}
\end{landscape}

\section{Conclusion}\label{sec:concl}

	In this thesis,
    we analyzed RePair\xspace and showed
    that RePair\xspace replaces step by step the most frequent pairs within the corresponding most frequent maximal repeats.
    Motivated by this analysis,
	we designed a novel variant of RePair\xspace, called MR-RePair\xspace,
	which is based on substituting the most frequent maximal repeats at once
    instead of substituting the most frequent pairs consecutively.
	Moreover, we implemented MR-RePair\xspace and compared the grammar generated by it to that by RePair\xspace for several texts,
	and confirmed the effectiveness of MR-RePair\xspace experimentally especially for highly repetitive texts.

    We defined the greatest size difference of any two possible grammars that can be generated by RePair for a given text, and named it as GSDRP.
    Moreover, we showed that a lower bound of GSDRP is $\frac{1}{6}(\sqrt{6n+1}+13)$ for a given text of length $n$.
    Improving the lower bound and showing a upper bound of GSDRP are our future works.

    Although we did not discuss how to encode grammars,
    it is a very important issue from a practical point of view.
    For MR-RePair\xspace, if we simply use delimiters to store the rule set,
    the number of rules may drastically affect the compressed data size.
    To develop an efficient encoding method for MR-RePair\xspace is one of our future works.

\section{Experiments}\label{sec:exp}

We implemented MR-RePair\xspace and measured the number of generated rules and the execution time
in order to compare it to existing RePair\xspace implementations and
Re-PairImp\footnote{\url{https://bitbucket.org/IguanaBen/repairimproved}}
proposed by Ga{\'n}czorz and Je{\.z}~\cite{ganczorz2017improvements}.

As stated in Remark~\ref{rem:order},
the size of a generated grammar depends on the MR-order.
In practice, the MR-order varies how we implement the priority queue managing symbol pairs.
To see this, we used five RePair\xspace implementations in the comparison;
they were implemented by
Maruyama\footnote{\url{https://code.google.com/archive/p/re-pair/}},
Navarro\footnote{\url{https://www.dcc.uchile.cl/~gnavarro/software/index.html}},
Prezza\footnote{\url{https://github.com/nicolaprezza/Re-Pair}}~\cite{7921912},
Wan\footnote{\url{https://github.com/rwanwork/Re-Pair}; We ran it with level 0 (no heuristic option).},
and Yoshida%
\footnote{\url{https://github.com/syoshid/Re-Pair-VF}; We removed a routine to find the best rule set.}.

Table~\ref{tbl:used_text} summarizes the details of the texts we used in the comparison.
We used three texts as highly repetitive texts;
one is a randomly generated text (rand77.txt),
and the others are a Fibonacci string (fib41)
and a German text (einstein.de.txt) which were selected from Repetitive Corpus of Pizza\&Chili Corpus%
\footnote{\url{http://pizzachili.dcc.uchile.cl/repcorpus.html}}.
The randomly generated text, rand77.txt, consists of alphanumeric symbols and some special symbols;
and it is generated by concatenating 32 copies of a block that includes 1024 random patterns of length 64,
i.e., the size is $64\times 1024\times 32=2,097,152$ byte.
In addition, we used three texts (E.coli, bible.txt, world192.txt) for real data selected from Large Corpus%
\footnote{\url{http://corpus.canterbury.ac.nz/descriptions/\#large}}.
We executed each program seven times for each text and measured the elapsed CPU time only for grammar generation process.
We calculated the average time of the five results excluding the minimum and maximum values among seven.
We ran our experiments on a workstation equipped with an Intel(R) Xeon(R) E5-2670 2.30GHz dual CPU with 64GB RAM, running on Ubuntu 16.04LTS on Windows 10.
All the programs are compiled by gcc version 7.3.0 with ``-O3'' option.

\begin{table*}[tb]

	\begin{center}
		\caption{Text files used in our experiments.}%
		\vspace{12pt}
		\label{tbl:used_text}
		\begin{tabular}{l@{\quad}r@{\quad}r@{\quad}l}
			\hline
			\multicolumn{1}{c}{texts~~~~} & \multicolumn{1}{c}{size (bytes)~~} & \multicolumn{1}{c}{$|\Sigma|$~~} & \multicolumn{1}{c}{contents~~~~}                      \\
			\hline
			rand77.txt                    & 2,097,152                         & 77                               & 32 copies of 1024 random patterns of length 64        \\
			fib41                         & 267,914,296                       & 2                                & Fibonacci string from Pizza\&Chili Corpus             \\
			einstein.de.txt               & 92,758,441                        & 117                              & Edit history of Wikipedia for Albert Einstein \\
			E.coli                        & 4,638,690                         & 4                                & Complete genome of the E. Coli bacterium              \\
			bible.txt                     & 4,047,392                         & 63                               & The King James version of the bible                   \\
			world192.txt                  & 2,473,400                         & 94                               & The CIA world fact book                               \\
			\hline
		\end{tabular}
	\end{center}
	\vspace{-12pt}

\end{table*}

Table~\ref{tbl:exp_res_v2} lists the experimental results.
Here, we excluded the number of rules that generate a single terminal symbol from the number of rules
because it is the same between MR-RePair\xspace and RePair\xspace.
As shown in the table,
for all texts except for fib41,
the size of rules generated by each RePair\xspace implementation differs from each other.%
\footnote{We found that the results of Yoshida were the same as those of Maruyama because Yoshida utilized the code of Maruyama.}.
In any case, MR-RePair\xspace is not inferior to RePair\xspace in the size of rules.
For rand77.txt in particular,
the number of rules decreased to about 11\% and the size of rules decreased to about 55\%.
For einstein.de.txt, moreover,
the number of rules decreased to about 44\% and the size of rules decreased to about 72\%.
On the other hand, for the texts of Large Corpus, which are not highly repetitive,
it turned out that the effect of improvement was limited.
Note that fib41 does not contain any maximal repeats longer than 2 without overlaps.
Therefore, MR-RePair\xspace generates the same rules as RePair\xspace.
Also note that MR-RePair\xspace runs at a speed comparable to the fastest implementation of RePair\xspace.

\input{table}

\section{Introduction}

Grammar compression is a method of lossless data compression
that reduces the size of a given text
by constructing a small context free grammar that uniquely derives the text.
While the problem of generating the smallest such grammar is NP-hard~\cite{1459058},
several approximation techniques have been proposed.
Among them, RePair\xspace~\cite{892708} is known as an off-line method
that achieves a high compression ratio in practice~\cite{claude2010fast, gonzalez2007compressed, wan2003browsing},
despite its simple scheme.
There have been many studies concerning RePair\xspace, such as
extending it to an online algorithm~\cite{7786179},
improving its practical working time or space~\cite{7921912, sekine2014adaptive},
applications to other fields~\cite{claude2010fast, lohrey2013xml, tabei2016scalable},
and analyzing the generated grammar size theoretically~\cite{1459058,navarro2008re,Ochoa2018}.

Recently, maximal repeats have been considered as
a measure for estimating how repetitive a given string is:
Belazzougui et al.~\cite{10.1007/978-3-319-19929-0_3} showed that
the number of extensions of maximal repeats is an upper bound on
the number of runs in the Burrows-Wheeler transform
and the number of factors in the Lempel-Ziv parsing.
Also, several index structures whose size is bounded
by the number of extensions of maximal repeats
have been proposed~\cite{belazzougui2017fast, DBLP:conf/cpm/BelazzouguiC17, 10.1007/978-3-319-67428-5_26}.

In this paper,
we analyze the properties of RePair\xspace with regard to its relationship to maximal repeats.
As stated above, several works have studied RePair\xspace,
but, to the best of our knowledge,
none of them associate RePair\xspace with maximal repeats.
Moreover,
we propose a grammar compression algorithm,
called MR-RePair\xspace,
that focuses on the property of maximal repeats.
Ahead of this work,
several off-line grammar compression schemes focusing on (non-maximal) repeats
have been proposed~\cite{apostolico2000off, inenaga2003linear, 4148751}.
Very recently,
Ga{\'n}czorz and Je{\.z} addressed to heuristically improve the compression ratio of RePair\xspace
with regard to the grammar size~\cite{ganczorz2017improvements}.
However, none of these techniques use the properties of maximal repeats.
We show that, under a specific condition,
there is a theoretical guarantee that
the size of the grammar generated by MR-RePair\xspace is smaller than or equal to that
generated by RePair\xspace.
We also confirmed the effectiveness of MR-RePair\xspace compared to RePair\xspace through computational experiments.

\noindent
{\bf Contributions:} The primary contributions of this study are as follows.
\begin{enumerate}
	\item
	We analyze RePair\xspace and show the relation between a grammar generated by RePair\xspace and maximal repeats.
	\item
	We design a novel variant of RePair\xspace called MR-RePair\xspace,
		which is based on substituting the most frequent maximal repeats.
	\item
	We implemented our MR-RePair\xspace algorithm and experimentally confirmed
		that MR-RePair\xspace reduces the size of the generated grammar compared to RePair\xspace;
		in particular, the size decreased to about 55\% for a highly repetitive text that we used in our experiment.
\end{enumerate}

The remainder of this paper is organized as follows.
In Section~\ref{sec:prelim},
we review the notations of strings and the definitions of maximal repeats, grammar compression, and RePair\xspace.
In Section~\ref{sec:repair},
we analyze RePair\xspace and show the relation between RePair\xspace and maximal repeats.
In Section~\ref{sec:mrrepair},
we define MR-RePair\xspace,
compare it with RePair\xspace,
and describe the implementation of it.
In Section~\ref{sec:exp},
we present experimental results of comparison to RePair\xspace.
Finally, we conclude the paper in Section~\ref{sec:concl}.

\section{MR-RePair\xspace}\label{sec:mrrepair}

The main strategy of our proposed method is to
recursively replace the most frequent maximal repeats,
instead of the most frequent pairs.

In this section,
first,
we explain the na\"{\i}ve version of our method called Na\"{\i}ve-MR-RePair\xspace.
While it can have bad performance in specific cases,
it is simple and helpful to understand our main result.
Then, we describe our proposed MR-RePair\xspace.

\subsection{Na\"{\i}ve-MR-RePair\xspace}

\begin{Definition}[Na\"{\i}ve-MR-RePair\xspace]\label{def:nmr}

  For input text $T$,
	let $G=\set{V,\Sigma ,S,R}$ be the grammar generated by Na\"{\i}ve-MR-RePair\xspace.
	Na\"{\i}ve-MR-RePair\xspace constructs $G$ by the following steps:\\

	\noindent
	{\bf Step~1.} Replace each symbol $a\in \Sigma$ with a new variable $v_a$ and add $v_a\rightarrow a$ to $R$.\\
	{\bf Step~2.} Find the most frequent maximal repeat $r$ in $T$.\\
  {\bf Step~3.} Replace every occurrence (or, as many occurrences as possible, when there are overlaps)
  of $r$ in $T$ with a new variable $v$,
	and then add $v \rightarrow r$ to $R$.\\
	{\bf Step~4.} Re-evaluate the frequencies of maximal repeats
	for the renewed text generated in {\bf Step~3}.
	If the maximum frequency is 1,
	add $S \rightarrow {\rm (current~text)}$ to $R$,
	and terminate.
	Otherwise, return to {\bf Step~2}.

\end{Definition}

We can easily extend the concept of MR-order\xspace
to this Na\"{\i}ve-MR-RePair\xspace.

\begin{figure*}[tb]

	\centering
	\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|}
		\cline{2-12}
		                                                                              & {\tt a}                    & {\tt b}           & {\tt r}           & {\tt a}           & {\tt c}           & {\tt a}           & {\tt d}           & {\tt a}           & {\tt b}           & {\tt r}           & {\tt a}           \\ \cline{2-12} \noalign{\vspace{2pt}} \hline
		\multicolumn{1}{|c||}{$v_{\alpha} \rightarrow \alpha~(\alpha = {\rm {\tt a,b,r,c,d}})$}
		                                                                              & $v_{\rm {\tt a}}$          & $v_{\rm {\tt b}}$ & $v_{\rm {\tt r}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt c}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt d}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt b}}$ & $v_{\rm {\tt r}}$ & $v_{\rm {\tt a}}$ \\ \hline
		\multicolumn{1}{|c||}{$v_1 \rightarrow v_{\rm {\tt a}}v_{\rm {\tt b}}v_{\rm {\tt r}}v_{\rm {\tt a}}$}
		                                                                              & \multicolumn{4}{c|}{$v_1$} & $v_{\rm {\tt c}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt d}}$
		                                                                              & \multicolumn{4}{c|}{$v_1$}                                                                                \\ \hline
		\multicolumn{1}{|c||}{$S \rightarrow v_1v_{\rm {\tt c}}v_{\rm {\tt a}}v_{\rm {\tt d}}v_1$} & \multicolumn{11}{c|}{$S$}                                                                                \\ \hline
	\end{tabular}
	\caption{An example of the grammar generation process of Na\"{\i}ve-MR-RePair\xspace for text {\tt abracadabra}.
	The generated grammar is
	$\set{
		\set{v_{\rm {\tt a}},v_{\rm {\tt b}},v_{\rm {\tt r}},v_{\rm {\tt c}},v_{\rm {\tt d}}, v_1, S},
		\set{{\rm {\tt a},{\tt b},{\tt r},{\tt c},{\tt d}}}, S,
		\set{v_{\rm {\tt a}}\rightarrow {\rm {\tt a}},
		v_{\rm {\tt b}}\rightarrow {\rm {\tt b}},
		v_{\rm {\tt r}}\rightarrow {\rm {\tt r}},
		v_{\rm {\tt c}}\rightarrow {\rm {\tt c}},
		v_{\rm {\tt d}}\rightarrow {\rm {\tt d}},
		v_1 \rightarrow v_{\rm {\tt a}}v_{\rm {\tt b}}v_{\rm {\tt r}}v_{\rm {\tt a}},
		S \rightarrow v_1v_{\rm {\tt c}}v_{\rm {\tt a}}v_{\rm {\tt d}}v_1}
		}$,
	and the grammar size is $14$.
	}
	\label{fig:abranmr}
\end{figure*}

We show an example of the grammar generation
process of Na\"{\i}ve-MR-RePair\xspace in Figure~\ref{fig:abranmr}.
Figure~\ref{fig:abrarp}~and~\ref{fig:abranmr} illustrates
the intuitive reason why the strategy using maximal repeats is effective
compared to that using pairs.
When compressing text
$v_{\tt a}v_{\tt b}v_{\tt r}v_{\tt a}v_{\tt c}v_{\tt a}v_{\tt d}v_{\tt a}v_{\tt b}v_{\tt r}v_{\tt a}$,
RePair\xspace and Na\"{\i}ve-MR-RePair\xspace both generate subgrammars which derive the most frequent maximal repeat
$v_{\tt a}v_{\tt b}v_{\tt r}v_{\tt a}$.
The rule set of the subgrammar of RePair\xspace is
$\{v_1 \rightarrow v_{\tt a}v_{\tt b}, v_2 \rightarrow v_1v_{\tt r}, v_3 \rightarrow v_2v_{\tt a} \}$,
and the size is 6.
On the other hand,
the rule set of subgrammar of Na\"{\i}ve-MR-RePair\xspace is
$\{v_1 \rightarrow v_{\tt a}v_{\tt b}v_{\tt r}v_{\tt a}\}$,
and the size is 4.

However, the following theorem indicates that
the size of the grammar generated by Na\"{\i}ve-MR-RePair\xspace is larger than that by RePair\xspace
in particular cases, even when they work in the same MR-order\xspace.

\begin{theorem}\label{theo:naive}
	Given a text $T$ with length $n$, and
	assume that RePair\xspace and Na\"{\i}ve-MR-RePair\xspace work in the same MR-order\xspace.
	Let $\gsize{rp}$ and $\gsize{nmr}$ be sizes of
	grammars generated by RePair\xspace and Na\"{\i}ve-MR-RePair\xspace for $T$, respectively.
	Then, there is a case where $\gsize{nmr} = \gsize{rp} + \mathcal{O}(\log n)$ holds.%
	\footnote{We show a concrete example of this theorem in Appendix.}
\end{theorem}

\begin{proof}

	Assume that $\gram{rp} = \set{\var{rp}, \sym{rp}, \stt{rp}, \rul{rp}}$
	and $\gram{nmr} = \set{\var{nmr}, \sym{nmr}, \stt{nmr}, \rul{nmr}}$
	are grammars generated by RePair\xspace and Na\"{\i}ve-MR-RePair\xspace, respectively.
	Let $T' = v_1\cdots v_n$ such that
	$v_i\in\var{rp}\cap\var{nmr}$ and $v_i \rightarrow T[i]\in\rul{rp}\cap\rul{nmr}$ (for $i = 1,\cdots , n$),
	and
	$\sgram{rp} = \set{\svar{rp}, \ssym{rp}, \sstt{rp}, \srul{rp}}$
	(or $\sgram{nmr} = \set{\svar{nmr}, \ssym{nmr}, \sstt{nmr}, \srul{nmr}}$)
	be a subgrammar of $\gram{rp}$ (or $\gram{nmr}$)
	which derives $T'$.
	Assume that
	$T' = (uw)^{2^{m+1}-1} u$,
	where $u\in \var{rp}\cap\var{nmr}$, $w\in (\var{rp}\cap\var{nmr})^{+}$
	such that $uwu$ is the most frequent maximal repeat of $T'$,
	and $m \in \mathbb{N}^{+}$.
	Note that $2^{m+1}-1 = \sum_{i=0}^{m}2^i$.
	Here $\srul{rp}$ and $\srul{nmr}$ consist as follows:
	\vspace{6pt}
	\begin{description}
		\item[$\srul{rp}$:]
		      Assume that $x_i\in \svar{rp}$ for $1\le i\le m$
		      and $y_j\in \svar{rp}\cup\ssym{rp}$ for $1\le j\le |w|$, then
		      \begin{itemize}
			      \item $|w|$ rules
			            $y_j\rightarrow y_ly_r$ with $\derive{y_{|w|}} = uw$.
			      \item
			            One rule $x_1\rightarrow y_{|w|}y_{|w|}$ and
			            $\log_2{\lfloor 2^{m+1}-1\rfloor}-1 = m-1$ rules
			            $x_i\rightarrow x_{i-1}x_{i-1}$ for $2\le i\le m$.
			      \item One rule
			            $\sstt{rp}\rightarrow x_{m} x_{m-1}\cdots x_{1}y_{|w|}$.
		      \end{itemize}
		\item[$\srul{nmr}$:]
		      Assume that $d = |\svar{nmr}| = |\srul{nmr}|$ and $z_i\in \svar{nmr}$ for $1\le i\le d$, then
		      \begin{itemize}
			      \item One rule $z_1 \rightarrow uwu$.
			      \item $d - 1$ rules
			            $z_i \rightarrow z_{i-1}wz_{i-1}$ for $2\le i\le d$
			            and $z_d = \sstt{nmr}$.
		      \end{itemize}
	\end{description}
	\vspace{6pt}
	Let $\sgsize{rp}$ and $\sgsize{nmr}$ be sizes of $\sgram{rp}$ and $\sgram{nmr}$, respectively.
	Then, the following holds:
	\begin{align}
		\sgsize{rp}  & = 2|w|+2m+(m+2)=3m+2|w|+2\label{eq:rpsize}        \\
		\sgsize{nmr} & = |w|+2+(|w|+2)(d-1) = (|w|+2)d\label{eq:nmrsize}
	\end{align}
	Here, with regard to the length of $T'$, the following holds:
	\begin{equation*}
		(2^d-1)|w|+2^d = n = (2(2^m-1)+1)(|w|+1)+1.
	\end{equation*}
	Since the right-side results in $2^{m+1}|w|+2^{m+1}$,
	$d = m+1$ follows it.
	Hence, by equation~(\ref{eq:rpsize}) and (\ref{eq:nmrsize}), the following holds:
	\begin{equation*}
		\sgsize{nmr}-\sgsize{rp}=(m - 1)(|w| - 1) - 1.
	\end{equation*}
	Therefore, $\sgsize{nmr} > \sgsize{rp}$ holds for some $(m, |w|)$,
	and the proposition holds.

\end{proof}

\subsection{MR-RePair\xspace}

The reason why the grammar size of Na\"{\i}ve-MR-RePair\xspace becomes larger than that of RePair\xspace as seen in Theorem~\ref{theo:naive} is
that Na\"{\i}ve-MR-RePair\xspace cannot replace all occurrences of the most frequent maximal repeats
if it overlaps with another occurrence of itself.
In the remainder of this section,
we describe MR-RePair\xspace, which is an improved version of the above Na\"{\i}ve-MR-RePair\xspace.

\begin{Definition}[MR-RePair\xspace]\label{def:mr}

  For input text $T$,
  let $G=\set{V,\Sigma ,S,R}$ be the grammar generated by MR-RePair\xspace.
  MR-RePair\xspace constructs $T$ by the following steps:\\

\vspace{-10pt}
	\noindent
	{\bf Step~1.} Replace each symbol $a\in \Sigma$ with a new variable $v_a$ and add $v_a\rightarrow a$ to $R$.\\
	{\bf Step~2.} Find the most frequent maximal repeat $r$ in $T$.\\
	{\bf Step~3.} Check if $|r|>2$ and $r[1]=r[|r|]$, and
	if so, replace $r$ with $r[2..|r|]$. \\

	{\bf Step~4.} Replace every occurrence of $r$ with a new variable $v$,
	then add $v \rightarrow r$ to $R$.\\
	{\bf Step~5.} Re-evaluate the frequencies of maximal repeats
	for the renewed text generated in {\bf Step~4}.
	If the maximum frequency is 1,
	add $S \rightarrow {\rm (current~text)}$ to $R$, and terminate.
	Otherwise, return to {\bf Step~2}.

\end{Definition}

\begin{figure*}[tb]

	\centering
	\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|}
		\cline{2-12}
		                                                                              & {\tt a}                    & {\tt b}           & {\tt r}           & {\tt a}           & {\tt c}           & {\tt a}           & {\tt d}           & {\tt a}           & {\tt b}           & {\tt r}           & {\tt a}           \\ \cline{2-12} \noalign{\vspace{2pt}} \hline
		\multicolumn{1}{|c||}{$v_{\alpha} \rightarrow \alpha~(\alpha = {\rm {\tt a,b,r,c,d}})$}
		                                                                              & $v_{\rm {\tt a}}$          & $v_{\rm {\tt b}}$ & $v_{\rm {\tt r}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt c}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt d}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt b}}$ & $v_{\rm {\tt r}}$ & $v_{\rm {\tt a}}$ \\ \hline
		\multicolumn{1}{|c||}{$v_1 \rightarrow v_{\rm {\tt a}}v_{\rm {\tt b}}v_{\rm {\tt r}}$}
		                                                                              & \multicolumn{3}{c|}{$v_1$} & $v_{\rm {\tt a}}$ & $v_{\rm {\tt c}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt d}}$
		                                                                              & \multicolumn{3}{c|}{$v_1$} & $v_{\rm {\tt a}}$                                                                                \\ \hline
		\multicolumn{1}{|c||}{$v_2 \rightarrow v_1v_{\rm {\tt a}}$}
		                                                                              & \multicolumn{4}{c|}{$v_2$} & $v_{\rm {\tt c}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt d}}$
		                                                                              & \multicolumn{4}{c|}{$v_2$}                                                                                \\ \hline
		\multicolumn{1}{|c||}{$S \rightarrow v_2v_{\rm {\tt c}}v_{\rm {\tt a}}v_{\rm {\tt d}}v_2$} & \multicolumn{11}{c|}{$S$}                                                                                \\ \hline
	\end{tabular}
	\caption{An example of the grammar generation process of MR-RePair\xspace for text {\tt abracadabra}.
	The generated grammar is
	$\set{
		\set{v_{\rm {\tt a}},v_{\rm {\tt b}},v_{\rm {\tt r}},v_{\rm {\tt c}},v_{\rm {\tt d}}, v_1, S},
		\set{{\rm {\tt a},{\tt b},{\tt r},{\tt c},{\tt d}}}, S,
		\set{v_{\rm {\tt a}}\rightarrow {\rm {\tt a}},
		v_{\rm {\tt b}}\rightarrow {\rm {\tt b}},
		v_{\rm {\tt r}}\rightarrow {\rm {\tt r}},
		v_{\rm {\tt c}}\rightarrow {\rm {\tt c}},
		v_{\rm {\tt d}}\rightarrow {\rm {\tt d}},
		v_1 \rightarrow v_{\rm {\tt a}}v_{\rm {\tt b}}v_{\rm {\tt r}},
		v_2 \rightarrow v_1v_{\rm {\tt a}},
		S \rightarrow v_2v_{\rm {\tt c}}v_{\rm {\tt a}}v_{\rm {\tt d}}v_2}
		}$,
	and the grammar size is $15$.
	}%
	\vspace{-10pt}
	\label{fig:abramr}
\end{figure*}

We show an example of the grammar generation process of MR-RePair\xspace in Figure~\ref{fig:abramr}.
We can easily extend the concept of MR-order\xspace to this MR-RePair\xspace.
We do not care if it uses $r[1..|r-1|]$ in {\bf Step 3}, instead of $r[2..|r|]$.
MR-RePair\xspace can replace all occurrences of $r$
even if it overlaps with itself in some occurrences,
since by Lemma~\ref{lem:lenol},
the length of overlaps of the most frequent maximal repeats is at most 1.
If $r[1] = r[|r|]$ but $r$ does not overlap with itself,
then $r[1]v$ becomes the most frequent maximal repeat after $r[2..|r|]$ is replaced by $v$,
and $r[1]v$ would be replaced immediately.
MR-RePair\xspace still cannot replace all of them if $|r|=2$,
but the same is said to RePair\xspace.

We show an example of the grammar generation process of MR-RePair\xspace in Figure~\ref{fig:abramr}.
Although the size of the generated grammar in Figure~\ref{fig:abramr} is larger than that of Na\"{\i}ve-MR-RePair\xspace
shown in Figure~\ref{fig:abranmr},
it is still smaller than that of RePair\xspace shown in Figure~\ref{fig:abrarp}.

\begin{theorem}\label{theo:ratio}
	Assume that RePair\xspace and MR-RePair\xspace work based on the same MR-order\xspace for a given text.
	Let $\gsize{rp}$ and $\gsize{mr}$ be sizes of grammars
	generated by RePair\xspace and MR-RePair\xspace, respectively.
	Then,
	$\frac{1}{2} \gsize{rp} < \gsize{mr} \le \gsize{rp}$ holds.
\end{theorem}

\begin{proof}

	Assume that
	$\gram{rp} = \set{\var{rp}, \sym{rp}, \stt{rp}, \rul{rp}}$
	and $\gram{mr} = \set{\var{mr}, \sym{mr}, \stt{mr}, \rul{mr}}$
	are grammars generated by RePair\xspace and MR-RePair, respectively,
	for a given text $T$ with length $n$.
	Let $T' = v_1\cdots v_n$ such that
	$v_i\in\var{rp}\cap\var{mr}$ and $v_i \rightarrow T[i]\in\rul{rp}\cap\rul{mr}$ (for $i = 1,\cdots , n$).

	We start with $T'$.
	Let $f_1$ be the maximum frequency of maximal repeats in $T'$.
	By Corollary~\ref{coro:pm}, the maximum frequency of pairs in $T'$ is also $f_1$.
	Let $\sgram{rp}^{(f_1)}$ (or $\sgram{mr}^{(f_1)}$) be a subgrammar of $\gram{rp}$ (or $\gram{mr}$)
	which is generated while RePair\xspace (or MR-RePair\xspace) replaces pairs (or maximal repeats) with frequency $f_1$,
	$\sgsize{rp}^{(f_1)}$ (or $\sgsize{mr}^{(f_1)}$) be the size of it, and
	$T^{(f_1)}_{\mathit{rp}}$ (or $T^{(f_1)}_{\mathit{mr}}$) be the renewed text
	after all pairs (or maximal repeats) with frequency $f_1$ are replaced.
	Let $r_1^{(f_1)}, \cdots, r_{m_1}^{(f_1)}$ be maximal repeats with frequency $f_1$ in $T'$,
	and assume that they are prioritized in this order by the MR-order\xspace.

	Let each $l_i^{(f_1)}$ (for $i = 1,\cdots ,m_1$) be the length of the longest substring of $r_i^{(f_1)}$
	such that there are variables that derive the substring in both $\sgram{rp}^{(f_1)}$ and $\sgram{mr}^{(f_1)}$.
	Note that this substring is common to RePair\xspace and MR-RePair\xspace,
	and each $l_i^{(f_1)}$ is at least 2.
	Then, by Lemma~\ref{lem:pm}, the following holds:
	\begin{align*}
		\sgsize{rp}^{(f_1)} &= \sum_{i=1}^{m_1} 2(l_i^{(f_1)}-1)~,~~~\\
		\sgsize{mr}^{(f_1)} &= \sum_{i=1}^{m_1} l_i^{(f_1)}. ~~~
	\end{align*}
	Therefore,
	\begin{align}
		\therefore ~ \frac{1}{2}\sgsize{rp}^{(f_1)} < \sgsize{mr}^{(f_1)} \le \sgsize{rp}^{(f_1)}\label{eq:f1}
	\end{align}
	holds.
	The renewed texts $T^{(f_1)}_{\mathit{rp}}$ and $T^{(f_1)}_{\mathit{mr}}$ are isomorphic for $\var{rp}$ and $\var{mr}$.
	Let $f_2$ be the maximum frequency of maximal repeats in $T^{(f_1)}_{\mathit{rp}}$
	(and this is the same in $T^{(f_1)}_{\mathit{mr}}$).
	Then, the similar discussion holds for $\sgram{rp}^{(f_2)}$ and $\sgram{mr}^{(f_2)}$.
	Hence, $\frac{1}{2}\sgsize{rp}^{(f_2)} < \sgsize{mr}^{(f_2)} \le \sgsize{rp}^{(f_2)}$ holds
	similarly to (\ref{eq:f1}),
	and the renewed texts $T^{(f_2)}_{\mathit{rp}}$ and $T^{(f_2)}_{\mathit{mr}}$ are isomorphic.
	Inductively, for every maximum frequency of maximal repeats $f_i$,
	$\frac{1}{2}\sgsize{rp}^{(f_i)} < \sgsize{mr}^{(f_i)} \le \sgsize{rp}^{(f_i)}$ holds
	and the renewed texts $T^{(f_i)}_{\mathit{rp}}$ and $T^{(f_i)}_{\mathit{mr}}$ are isomorphic.
	Let $k$ be a natural number such that $f_k > 1$ and $f_{k+1} = 1$,
	which is the number of decreasing of maximum frequency through the whole process of RePair\xspace and MR-RePair\xspace.
	Then,
	\begin{align}
		\gsize{rp} & = \sum_{j=1}^{k}\sgsize{rp}^{(f_j)} + |\Sigma| + |T^{(f_k)}_{\mathit{rp}}|
		           = \sum_{j=1}^{k}\sum_{i=1}^{m_j} 2(l_i^{(f_j)}-1) + |\Sigma| + |T^{(f_k)}_{\mathit{rp}}|~,\label{eq:grp} \\
		\gsize{mr} & = \sum_{j=1}^{k}\sgsize{mr}^{(f_j)} + |\Sigma| + |T^{(f_k)}_{\mathit{mr}}|
				   = \sum_{j=1}^{k}\sum_{i=1}^{m_j} l_i^{(f_j)} + |\Sigma| + |T^{(f_k)}_{\mathit{mr}}|~\label{eq:gmr}
	\end{align}
	holds.
	Because every $l_i^{(f_j)} \ge 2$ and $|T^{(f_k)}_{\mathit{rp}}| = |T^{(f_k)}_{\mathit{mr}}|$,
	$\frac{1}{2}\gsize{rp} < \gsize{mr} \le \gsize{rp}$
	follows (\ref{eq:grp}) and (\ref{eq:gmr})
	and the proposition holds.
	$\gsize{mr} = \gsize{rp}$ holds when every length of $l_i^{(f_j)}$ is 2.

\end{proof}

The following theorem shows that
unless the MR-order\xspace of RePair\xspace and MR-RePair\xspace are the same,
the grammar generated by MR-RePair\xspace might be larger than that by RePair\xspace.

\begin{theorem}
	Unless the MR-order\xspace of RePair\xspace and MR-RePair\xspace are the same,
	there is a case where
	the size of the generated grammar by MR-RePair\xspace becomes larger than that by RePair\xspace.
\end{theorem}

\begin{proof}

	As shown in Theorem~\ref{theo:ratio},
	the size of grammar generated by MR-RePair\xspace would be strictly equal to that by RePair\xspace with the same MR-order\xspace.

    Thus, we can reduce this problem to
    the problem that there is a difference between sizes of possible grammars generated by RePair\xspace as stated in Remark~\ref{rem:order}.
	Hence, there are the cases stated in the proposition
	if the MR-order\xspace of MR-RePair\xspace matches with a MR-order\xspace of RePair\xspace which does not generate the smallest RePair\xspace grammar.

\end{proof}

We can implement MR-RePair\xspace by extending the original implementation of RePair\xspace
stated in~\cite{892708},
holding the same complexity.

\begin{theorem}\label{theo:ts}
	Let $G=\set{V,\Sigma ,S,R}$ be the generated grammar by MR-RePair\xspace for a given text with length $n$.
	Then,
	MR-RePair\xspace works in $\mathcal{O} (n)$ expected time and
	$5n + 4k^2 + 4k^{\prime} + \lceil \sqrt{n + 1} \rceil - 1$ word space,
	where $k$ and $k'$ are the cardinalities of $\Sigma$ and $V$, respectively.
\end{theorem}

\begin{proof}

	Compared with RePair\xspace,
	the additional operations which MR-RePair\xspace does in our implementation are
	(i) it extends the selected pair to left and right until it becomes a maximal repeat, and
	(ii) it checks and excludes either of the beginning or the end of the obtained maximal repeat if they are the same.
	They can be realized by only using the same data structures as that of RePair\xspace.
	Then, the space complexity of MR-RePair\xspace follows Lemma~\ref{lem:rp}.

	We can clearly execute operation (ii) in constant time.
	So we consider how the time complexity is affected by operation (i).
	Let $l$ be the length of the maximal repeat containing the focused pair,
	and $f$ be the frequency of the pair.
	Then,
	when MR-RePair\xspace checks the left- and right-extensions for all occurrences of the focused pair,
	$\mathcal{O}(fl)$ excessive time is required compared with RePair\xspace.
	However, the length of entire text is shortened at least $f(l-1)$ by the replacement.
	Therefore, according to possible counts of replacement through the entire steps of the algorithm,
	MR-RePair\xspace works in $\mathcal{O}(n)$ expected time.

\end{proof}

\begin{Remark}

	We can convert a grammar of RePair\xspace to that of MR-RePair\xspace by repeating the following transform:
	If a variable $v$ appears only once on the right-hand side of other rules,
	remove the rule for $v$ and replace the one occurrence of $v$ with the right-hand side of the removed rule.
	However, time and space complexity stated in Theorem~\ref{theo:ts} cannot be achieved in this manner,
	since additional operations and memory for searching and storing such variables are required.

\end{Remark}

\section{Preliminaries}\label{sec:prelim}

In this sections, we provide some notations and definitions to be used in the following sections.
In addition, we recall grammar compression and review the RePair\xspace.

\subsection{Basic notations and terms}
Let $\Sigma$ be an {\em alphabet}, which is an ordered finite set of symbols.
An element $T = t_1 \cdots t_n$ of $\Sigma^{*}$ is called a {\em string},
where $|T| = n$ denotes its length.
We denote the empty string by $\epsilon$ which is the string of length $0$, namely, $|\epsilon| = 0$.
Let $\Sigma^{+} = \Sigma^{*} \backslash \{{\epsilon}\}$.
A string is also called a {\em text}.
Let $T = t_1 \cdots t_n \in \Sigma^{n}$ be any text of length $n$.
If $T = usw$ with $u,s,w\in\Sigma^{*}$, then $s$ is called a {\em substring} of $T$.
Then, for any $1 \le i \le j \le n$,
let $T[i..j] = t_i \cdots t_j$ denote the substring of $T$ that begins and ends at positions $i$ and $j$ in $T$,
and let $T[i] = t_i$ denote the $i$th symbol of $T$.
For a finite set $S$ of texts,
text $T$ is said a {\em superstring} of $S$,
if $T$ contains all texts of $S$ as substrings.
We call the number of occurrences of $s$ in a text as a substring, the {\em frequency} of $s$,
and denote it by $\occ{s}$.
Texts $\Sigma^{*}$ and $\hat{\Sigma}^{*}$ are said to be isomorphic for alphabet $\Sigma$ and $\hat{\Sigma}$,
if there exists an isomorphism from $\Sigma$ to $\hat{\Sigma}$.

\subsection{Maximal repeats}
Let $s$ be a substring of text $T$.
If the frequency of $s$ is greater than $1$,
$s$ is called a {\em repeat}.
A {\em left} (or {\em right}) {\em extension} of $s$ is
any substring of $T$ with the form $ws$ (or $sw$), where $w \in \Sigma^{*}$.
We say that $s$ is {\em left} (or {\em right}) {\em maximal}
if left (or right) extensions of $s$ occur strictly fewer times in $T$ than $s$, and
call $s$ a {\em maximal repeat} of $T$
if $s$ is left and right maximal.
We call $s$ a {\em maximal repeatg} of $T$
if both left- and right-extensions of $s$ occur strictly fewer times in $T$ than $s$.
In this thesis, we consider only such strings with length more than $1$
as maximal repeats.
For example, substring \texttt{abra} of $T=$\texttt{abracadabra} is a maximal repeat,
while \texttt{br} is not.

\subsection{Grammar compression}
A {\em context free grammar} (CFG or {\em grammar}, simply) $G$ is defined as
a 4-tuple $G = \{V, \Sigma, S, R\}$,
where $V$ is an ordered finite set of {\em variables},
$\Sigma$ is an ordered finite alphabet,
$R$ is a finite set of binary relations called {\em production rules} (or {\em rules})
between $V$ and $(V \cup \Sigma)^{*}$,
and $S\in V$ is a special variable called {\em start variable}.
A production rule represents the manner in which a variable is substituted and written in
a form $v \rightarrow w$
with $v \in V$ and $w \in (V \cup \Sigma)^{*}$.
Let $X, Y \in {V\cup\Sigma}^{*}$.
If there are $x_l,x,x_r,y\in(V \cup \Sigma)^{*}$ such that $X=x_lxx_r$, $Y=x_lyx_r$, and $x\rightarrow y\in R$,
we write $X\Rightarrow Y$, and denote the reflexive transitive closure of $\Rightarrow$ by $\overset{*}{\Rightarrow}$.
Let $\derive{v}$ be the string derived from $v$, i.e., $v \overset{*}{\Rightarrow} \derive{v}$,
and let $\vari{w}$ denote a variable that derives $w$, i.e. $\vari{w}\overset{*}{\Rightarrow} w$.
Note that $\vari{w}$ is not necessarily unique.
We define grammar
$\hat{G} = \{\hat{V}, \hat{\Sigma}, \hat{S}, \hat{R}\}$
as a {\em subgrammar} of $G$
if $\hat{V} \subseteq V$, $\hat{\Sigma} \subseteq V\cup\Sigma$, and $\hat{R} \subseteq R$.

Given a text $T$,
{\em grammar compression} is a method of lossless text data compression
that constructs a restricted CFG,
which uniquely derives the given text $T$.
For $G$ to be deterministic,
a production rule for each variable $v\in V$ must be unique.
In what follows, we assume that every grammar is deterministic and
each production rule is
$v_i \rightarrow \mathit {expr}_i$,
where $\mathit{expr_i}$ is an expression
either $\mathit{expr}_i = a$ ($a \in \Sigma$)
or $\mathit{expr}_i = v_{j_1}v_{j_2}\cdots v_{j_n}$ (
$i > j_k$ for all $1\leq k \leq j_n$).

We estimate the effectiveness of compression by the size of generated grammar,
which is counted by the total length of the right-hand-side of all production rules of the generated grammar.

\subsection{RePair\xspace}
RePair\xspace is a grammar compression algorithm
proposed by Larsson and Moffat~\cite{892708}.
For input text $T$, let $G=\set{V,\Sigma ,S,R}$ be the grammar generated by RePair\xspace.
RePair\xspace constructs $G$ by the following steps:\\

	\noindent
	{\bf Step~1.} Replace each symbol $a\in \Sigma$ with a new variable $v_a$ and add $v_a\rightarrow a$ to $R$.\\
	{\bf Step~2.} Find the most frequent pair $p$ in $T$.\\
	{\bf Step~3.} Replace every occurrence (or, as many occurrences as possible, when $p$ is a pair consisting of the same symbol) of $p$ with a new variable $v$,
	then add $v \rightarrow p$ to $R$.\\
	{\bf Step~4.} Re-evaluate the frequencies of pairs	for the renewed text generated in {\bf Step~3}.
	If the maximum frequency is 1,
	add $S \rightarrow {\rm (current~text)}$ to $R$, and terminate.
	Otherwise, return to {\bf Step~2}. \\

\begin{figure*}[tb]
\centering
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c|}
\cline{2-12}
	& {\tt a} & {\tt b} & {\tt r} & {\tt a} & {\tt c} & {\tt a} & {\tt d} & {\tt a}  & {\tt b} & {\tt r} & {\tt a} \\ \cline{2-12} \noalign{\vspace{2pt}} \hline
	\multicolumn{1}{|c||}{$v_{\alpha} \rightarrow \alpha~(\alpha = {\rm {\tt a,b,r,c,d}})$}
& $v_{\rm {\tt a}}$ & $v_{\rm {\tt b}}$ & $v_{\rm {\tt r}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt c}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt d}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt b}}$ & $v_{\rm {\tt r}}$ & $v_{\rm {\tt a}}$ \\ \hline
\multicolumn{1}{|c||}{$v_1 \rightarrow v_{\rm {\tt a}}v_{\rm {\tt b}}$}
	& \multicolumn{2}{c|}{$v_1$} & $v_{\rm {\tt r}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt c}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt d}}$
	& \multicolumn{2}{c|}{$v_1$} & $v_{\rm {\tt r}}$ & $v_{\rm {\tt a}}$ \\ \hline
\multicolumn{1}{|c||}{$v_2 \rightarrow v_1v_{\rm {\tt r}}$}
	& \multicolumn{3}{c|}{$v_2$} & $v_{\rm {\tt a}}$ & $v_{\rm {\tt c}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt d}}$
	& \multicolumn{3}{c|}{$v_2$}         & $v_{\rm {\tt a}}$ \\ \hline
\multicolumn{1}{|c||}{$v_3 \rightarrow v_2v_{\rm {\tt a}}$} & \multicolumn{4}{c|}{$v_3$} & $v_{\rm {\tt c}}$ & $v_{\rm {\tt a}}$ & $v_{\rm {\tt d}}$
	& \multicolumn{4}{c|}{$v_3$}                 \\ \hline
\multicolumn{1}{|c||}{$S \rightarrow v_3v_{\rm {\tt c}}v_{\rm {\tt a}}v_{\rm {\tt d}}v_3$} & \multicolumn{11}{c|}{$S$} \\ \hline
\end{tabular}
\caption{An example of the grammar generation process of RePair\xspace for text {\tt abracadabra}.
	The generated grammar is
	$\set{
		\set{v_{\rm {\tt a}},v_{\rm {\tt b}},v_{\rm {\tt r}},v_{\rm {\tt c}},v_{\rm {\tt d}}, v_1, v_2, v_3, S},
		\set{{\rm {\tt a},{\tt b},{\tt r},{\tt c},{\tt d}}}, S,
		\set{v_{\rm {\tt a}}\rightarrow {\rm {\tt a}},
			v_{\rm {\tt b}}\rightarrow {\rm {\tt b}},
			v_{\rm {\tt r}}\rightarrow {\rm {\tt r}},
			v_{\rm {\tt c}}\rightarrow {\rm {\tt c}},
			v_{\rm {\tt d}}\rightarrow {\rm {\tt d}},
			v_1 \rightarrow v_{\rm {\tt a}}v_{\rm {\tt b}},
			v_2 \rightarrow v_1v_{\rm {\tt c}},
			v_3 \rightarrow v_2v_{\rm {\tt d}},
			S \rightarrow v_3v_{\rm {\tt c}}v_{\rm {\tt a}}v_{\rm {\tt d}}v_3}
	}$,
	and the grammar size is $16$.
	}%
\label{fig:abrarp}
\end{figure*}

Figure~\ref{fig:abrarp} shows an example of the grammar generation process of RePair\xspace.

\begin{lemma}[\cite{892708}]\label{lem:rp}
	RePair\xspace works in $\mathcal{O} (n)$ expected time and
	$5n + 4k^2 + 4k^{\prime} + \lceil \sqrt{n + 1} \rceil - 1$ words of space,
	where $n$ is the length of the source text,
	$k$ is the cardinality of the source alphabet, and
	$k^{\prime}$ is the cardinality of the final dictionary.
\end{lemma}

\section{Analyzing RePair\xspace}\label{sec:repair}

In this section,
we analyze RePair\xspace with regard to its relationship to maximal repeats,
and introduce an important concept, called MR-order\xspace.

\subsection{RePair\xspace and maximal repeats}

The following theorem shows an essential property of RePair\xspace.
That is, RePair\xspace recursively replaces the most frequent maximal repeats.

\begin{theorem}\label{theo:rpmr}
    Let $T$ be a given text,
    and assume that every most frequent maximal repeat of $T$ does not appear with overlaps with itself.
	Let $f$ be the frequency of the most frequent pairs of $T$, and
	$t$ be a text obtained after all pairs with frequency $f$ in $T$ are replaced by variables.
	Then, there is a text $s$ such that
	$s$ is obtained after all maximal repeats with frequency $f$ in $T$ are replaced by variables,
	and $s$ and $t$ are isomorphic to each other.
\end{theorem}

We need two lemmas and a corollary to prove Theorem~\ref{theo:rpmr}.
The following lemma shows a fundamental relation between the most frequent maximal repeats and
the most frequent pairs in a text.

\begin{lemma}\label{lem:pm}
	A pair $p$ of variables is most frequent in text $T$
	if and only if
	$p$ occurs once in exactly one of the most frequent maximal repeats of $T$.
\end{lemma}

\begin{proof}

	($\Rightarrow$)

	Let $r$ be a most frequent maximal repeat that contains $p$ as a substring.
	It is clear that $p$ can only occur once in $r$, since otherwise,
	$\occ{p} > \occ{r}$ would hold, implying the existence of a frequent maximal repeat that is more frequent than $r$,
	contradicting the assumption that $r$ is most frequent.
	Suppose there exists a different most frequent maximal repeat $r'$ that contains $p$ as a substring.
	Similarly, $p$ occurs only once in $r'$.
	Furthermore, since $r$ and $r'$ can be obtained by left and right extensions to $p$,
	$\occ{r} = \occ{r'} = \occ{p}$, and any occurrence of $p$ is contained in an occurrence of both $r$ and $r'$.
	Since $r'$ cannot be a substring of $r$, there exists some string $w$
	that is a superstring of $r$ and $r'$, such that $\occ{w} = \occ{r} = \occ{r'} = \occ{p}$.
	However, this contradicts that $r$ and $r'$ are maximal repeats.

	($\Leftarrow$)
	Let $r$ be the most frequent maximal repeat such that $p$ occurs once in.
	By definition, $\occ{r} = \occ{p}$.
	If $p$ is not the most frequent symbol pair in $T$, there exists some symbol pair $p'$ in $T$
	such that $\occ{p'} > \occ{p} = \occ{r}$.
	However, this implies that there is a maximal repeat $r'$ with $\occ{r'} = \occ{p'} > \occ{r}$,
	contradicting that $r$ is most frequent.

\end{proof}

The following corollary is directly derived from Lemma~\ref{lem:pm}.

\begin{corollary}\label{coro:pm}
	For a given text,
	the frequency of the most frequent pairs and that of the most frequent maximal repeats are the same.
\end{corollary}

The following lemma shows an important property of the most frequent maximal repeats.

\begin{lemma}\label{lem:lenol}
	The length of overlap between any two occurrences of most frequent maximal repeats is at most 1.
\end{lemma}

\begin{proof}

	Let $xw$ and $wy$ be most frequent maximal repeats that
	have an overlapping occurrence $xwy$,
	where $x,y,w\in\Sigma^{+}$.

	If $|w| \geq 2$, then, since $xw$ and $wy$ are most frequent maximal repeats,
	it must be that $\occ{w} = \occ{xw} = \occ{wy}$, i.e., every occurrence of
	$w$ is preceded by $x$ and followed by $y$.

	This implies that $\occ{xwy} = \occ{xw} = \occ{wy}$ as well,
	but contradicts that $xw$ and $wy$ are maximal repeats.

\end{proof}

From the above lemmas and a corollary, now we can prove Theorem~\ref{theo:rpmr}.

\vspace{-6pt}
\begin{proof}[Proof of Theorem~\ref{theo:rpmr}]

	By Corollary~\ref{coro:pm}, the frequency of the most frequent maximal repeats in $T$ is $f$.
	Let $p$ be one of the most frequent pairs in $T$.
	By Lemma~\ref{lem:pm}, there is a unique maximal repeat that is most frequent and contains $p$ once.
	We denote such maximal repeat by $r$.
	Assume that there is a substring $zxpyw$ in $T$,
	where $z,w\in \Sigma$, $x,y\in \Sigma^{*}$, and $xpy = r$.
	We denote $r[1]$ and $r[|r|]$ by $\dot{x}$ and $\dot{y}$, respectively.
	There are 2 cases to consider:

	\noindent {\bf (i) $\occ{z\dot{x}} < f$ and $\occ{\dot{y}w} < f$.}
	If $|r| = 2$, the replacement of $p$ directly corresponds to
	the replacement of the most frequent maximal repeat, since $p = r$.
	If $|r| > 2$, after $p$ is replaced with a variable $v$, $r$ is changed to $xvy$.
	This occurs $f$ times in the renewed text,
	and by Lemma~\ref{lem:pm}, the frequency of every pair occurring in $xvy$
	is still $f$.
	Because the maximum frequency of pairs does not increase, $f$ is still the maximum frequency.
	Therefore, we replace all pairs contained in $xvy$ in the following steps,
	and $z\dot{x}$ and $\dot{y}w$ are not replaced.
	This holds for every occurrence of $p$,
	implying that replacing the most frequent pairs while the
	maximum frequency does not change,
	corresponds to replacing all pairs contained (old and new)
	in most frequent maximal repeats of the same frequency
	until they are replaced by a single variable.
	Then, we can generate $s$ by replacement of $r$.

	\noindent {\bf (ii) $\occ{z\dot{x}} = f$ or $\occ{\dot{y}w} = f$.}
	We consider the case where $\occ{z\dot{x}} = f$.
	Note that $\occ{zxpy} < f$ by assumption that $xpy$ is a maximal repeat.
	Suppose RePair\xspace replaces $z\dot{x}$ by a variable $v$ before $p$ is replaced.
	Note that by Lemma~\ref{lem:pm}, there is a maximal repeat occurring $f$ times and including $z\dot{x}$ once
	(we denote the maximal repeat by $r'$),
	and $r' \neq r$ by assumption.
	By Lemma~\ref{lem:lenol}, the length of overlap of $r$ and $r'$ is at most 1, then only $\dot{x}$ is
	a symbol contained both $r$ and $r'$.
	After that, $xpy=r$ is no longer the most frequent maximal repeat
	because some of its occurrences are changed to $vr[2..|r|]$.
	However, $r[2..|r|]$ still occurs $f$ times in the renewed text.
	Since $\occ{zxpy}<f$ and $\occ{xpy}=f$, $\occ{vr[2]}<f$ and $r[2..|r|]$ is a maximal repeat.
	Then, $r[2..|r|]$ will become a variable in subsequent steps, similarly to {\bf (i)}.

	Here, $r'$ would also become a variable.
	Thus, we can generate $s$ in the way that we replace $r'$ first, then we replace $r[2..|r|]$.
	This holds similarly for $\dot{y}w$ when $\occ{\dot{y}w}=f$,
	and when $\occ{z\dot{x}} = \occ{\dot{y}w}=f$.

\end{proof}
\vspace{-6pt}

\subsection{MR-order\xspace}

From Theorem~\ref{theo:rpmr}, if the most frequent maximal repeat is unique in the current text,
then all the occurrences of it are replaced step by step by RePair\xspace.
However, it is a problem if there are two or more most frequent maximal repeats and some of them overlap.
In this case, which maximal repeat is first summarized up depends on
the order in which the most frequent pairs are selected.
Note, however, if there are multiple most frequent pairs,
which pair is first replaced depends on the implementation of RePair\xspace.
We call this order of selecting (summarizing) maximal repeats
{\em maximal repeat selection order} (or {\em MR-order\xspace}, simply).

For instance,
consider a text {\tt abcdeabccde}.
{\tt abc} and {\tt cde} are the most frequent maximal repeats occurring 2 times.
There are 2 MR-order\xspace,
depending on which one is attached priority to the other.
The results after replacement by RePair\xspace with the MR-order\xspace are
(i) $xyx{\tt c}x$ with variables $x$ and $y$ such that $x\overset{*}{\Rightarrow} {\tt abc}$ and $y\overset{*}{\Rightarrow} {\tt de}$, and
(ii) $zwz{\tt c}w$ with variables $z$ and $w$ such that $z\overset{*}{\Rightarrow} {\tt ab}$ and $w\overset{*}{\Rightarrow} {\tt cde}$.
More precisely,
there are 12 possible ways in which RePair\xspace can compress the text,
and the generated rule sets are:
\begin{enumerate}

	\item $\set{v_1\rightarrow {\tt ab}, v_2\rightarrow v_1{\tt c}, v_3\rightarrow {\tt de},
		S\rightarrow v_2v_3v_2{\tt c}v_3}$,
	\item $\set{v_1\rightarrow {\tt ab}, v_2\rightarrow {\tt de}, v_3\rightarrow v_1{\tt c},
		S\rightarrow v_3v_2v_3{\tt c}v_2}$,
	\item $\set{v_1\rightarrow {\tt bc}, v_2\rightarrow {\tt a}v_1, v_3\rightarrow {\tt de},
		S\rightarrow v_2v_3v_2{\tt c}v_3}$,
	\item $\set{v_1\rightarrow {\tt bc}, v_2\rightarrow {\tt de}, v_3\rightarrow {\tt a}v_1,
		S\rightarrow v_3v_2v_3{\tt c}v_2}$,
	\item $\set{v_1\rightarrow {\tt ed}, v_2\rightarrow {\tt ab}, v_3\rightarrow v_2{\tt c},
		S\rightarrow v_3v_1v_3{\tt c}v_1}$,
	\item $\set{v_1\rightarrow {\tt ed}, v_2\rightarrow {\tt bc}, v_3\rightarrow {\tt a}v_2,
		S\rightarrow v_3v_1v_3{\tt c}v_1}$,
	\item $\set{v_1\rightarrow {\tt ab}, v_2\rightarrow {\tt cd}, v_3\rightarrow v_2{\tt e},
		S\rightarrow v_1v_3v_1{\tt c}v_3}$,
	\item $\set{v_1\rightarrow {\tt ab}, v_2\rightarrow {\tt de}, v_3\rightarrow {\tt c}v_2,
		S\rightarrow v_1v_3v_1{\tt c}v_3}$,
	\item $\set{v_1\rightarrow {\tt cd}, v_2\rightarrow {\tt ab}, v_3\rightarrow v_1{\tt e},
		S\rightarrow v_2v_3v_2{\tt c}v_3}$,
	\item $\set{v_1\rightarrow {\tt cd}, v_2\rightarrow v_1{\tt e}, v_3\rightarrow {\tt ab},
		S\rightarrow v_3v_2v_3{\tt c}v_2}$,
	\item $\set{v_1\rightarrow {\tt ed}, v_2\rightarrow {\tt ab}, v_3\rightarrow {\tt c}v_1,
		S\rightarrow v_2v_3v_2{\tt c}v_3}$,
	\item $\set{v_1\rightarrow {\tt ed}, v_2\rightarrow {\tt c}v_1, v_3\rightarrow {\tt ab},
		S\rightarrow v_3v_2v_3{\tt c}v_2}$.

\end{enumerate}
Here, 1 - 6 have the same MR-order\xspace,
because ${\tt abc}$ is prior to ${\tt cde}$ in all of them.
On the other hand, 7 - 12 have the same MR-order\xspace for similar reason;
${\tt cde}$ is prior to ${\tt abc}$.

The size of the grammar generated by RePair\xspace varies according to
how to select a pair when there are several distinct most frequent pairs that overlap.
For instance,
consider the text
{\tt bcxdabcyabzdabvbcuda}.
There are 3 most frequent pairs,
${\tt ab}$, ${\tt bc}$, and ${\tt da}$
with 3 occurrences.
If RePair\xspace takes ${\tt ab}$ first,
the rule set of generated grammar may become
$\{v_1 \rightarrow {\tt ab},
~v_2 \rightarrow {\tt bc},
~v_3 \rightarrow {\tt d}v_1,
~S \rightarrow
v_2
{\tt x}
v_3
{\tt c}
{\tt y}
v_1
{\tt z}
v_3
{\tt v}
v_2
{\tt u}
{\tt d}
{\tt a}\}$
and the size of it is 19.
On the other hand,
if RePair\xspace takes ${\tt da}$ first,
the rule set of generated grammar may become
$\{v_1 \rightarrow {\tt da},
~v_2 \rightarrow {\tt bc},
~S \rightarrow
v_2
{\tt x}
v_1
v_2
{\tt y}
{\tt a}
{\tt b}
{\tt z}
v_1
{\tt b}
{\tt v}
v_2
{\tt u}
v_1
\}$
and the size of it is 18.

\begin{Remark}\label{rem:order}

	If there are several distinct pairs with the same maximum frequency,
	the size of the grammar generated by RePair\xspace depends on the replacement order of them.

\end{Remark}

However, the following theorem states that MR-order rather than the replacement order of pairs is essentially important for the size of the grammar generated by RePair\xspace.

\begin{theorem}\label{theo:order}
	The sizes of the grammars generated by RePair\xspace are the same
	if they are generated in the same MR-order\xspace.
\end{theorem}

\begin{proof}

	Let $T$ be a variable sequence appearing in the grammar generation process of RePair\xspace, and
	$f$ be the maximum frequency of pairs in $T$.
	Suppose that $T'$ is a variable sequence generated after RePair\xspace replaces every pair occurring $f$ times.
	By Theorem~\ref{theo:rpmr},
	all generated $T'$ are isomorphic to one another, then the length of all of them is the same,
	regardless of the replacement order of pairs.
	Let $r_1$ be the most frequent maximal repeats of $T$ such that $r_1$ is prior to all other ones in this MR-order\xspace.
	$r_1$ is converted into a variable as a result, and
	by Lemma~\ref{lem:pm}, all pairs included in $r_1$ are distinct.
	Then, the size of the subgrammar which exactly derives $r_1$ is $2(|r_1|-1)+1=2|r_1|-1$.
	This holds for the next prioritized maximal repeat (we denote it by $r_2$) with a little difference;
	the pattern actually replaced would be a substring of $r_2$
	excluding the beginning or the end of it, if there are occurrences of overlap with $r_1$.
	However, these strings are common in the same MR-order\xspace,
	then the sizes of generated subgrammars are the same,
	regardless of the selecting order of pairs.
	This similarly holds for all of the most frequent maximal repeats,
	for every maximum frequency of pairs,
	through the whole process of RePair\xspace.

\end{proof}

\subsection{Greatest size difference of RePair\xspace}

We consider the problem of how large the difference between possible outcomes of RePair\xspace can be.

\begin{Definition}[Greatest Size Difference]
	Let $g$ and $g'$ be sizes of any two possible grammars that can be generated by RePair\xspace for a given text.
	Then, the Greatest Size Difference of RePair\xspace (GSDRP) is ${\rm max}(|g - g'|)$.
\end{Definition}

We show a lower bound of above GSDRP in the following theorem.

\begin{theorem}\label{theo:gsgrpomega}
	Given a text with length $n$,
	a lower bound of GSDRP is $\frac{1}{6}(\sqrt{6n+1}+13)$.
\end{theorem}

\begin{proof}

	Let $B$, $L$, and $R$ be strings such that
	\begin{align*}
		B &= l_1 xy r_1 l_2 xy r_2
		\cdots \mathit{l_{f{\rm -1}}} xy \mathit{r_{f{\rm -1}}} \mathit{l_f} xy \mathit{r_f}, \\
		L &= \diamondsuit l_1 x\diamondsuit l_2 x \cdots \diamondsuit \mathit{l_f} x, ~~~\\
		R &= \diamondsuit y r_1\diamondsuit y r_2 \cdots \diamondsuit y \mathit{r_f},
	\end{align*}
  where
  $x,y,l_1, \ldots, l_f, r_1, \ldots, r_f$ denote distinct symbols,
  and each occurrence of $\diamondsuit$ denotes a distinct symbol.

  Consider text $T = BL^{f-1}R^{f-1}$.

	Here,
	$xy$, $l_1 x$, $\cdots$, $l_f x$, $\mathit{y r_1}$, $\cdots$, $\mathit{y r_f}$
  are the most frequent maximal repeats with frequency $f$ in $T$.

	Let $G$ and $G'$ be grammars generated by RePair\xspace for $T$ in different MR-order\xspace, such that
	(i) $xy$ is prior to all other maximal repeats, and
	(ii) $xy$ is posterior to all other maximal repeats, respectively.
	We denote the sizes of $G$ and $G'$ by $g$ and $g'$, respectively.

	First, we consider $G$ and how RePair\xspace generates it.
	The first rule generated by replacement is $v_1\rightarrow xy$ because of the MR-order\xspace.
	After replacement, $L$ and $R$ is unchanged but $B$ becomes the following text:
	\begin{equation*}
		B_1 = l_1 v_1 r_1 l_2 v_1 r_2
		\cdots \mathit{l_{f{\rm -1}}} v_1 \mathit{r_{f{\rm -1}}} \mathit{l_f} v_1 \mathit{r_f}.
	\end{equation*}

    Each pair in $B_1$ occurs only once in the whole text $B_1L^{f-1}R^{f-1}$.

	This means that $B_1$ is never be shortened from the current length, $3f$.
	In the remaining steps, each $\mathit{l_i}x$ and $y\mathit{r_i}$ (for $i = 1, \cdots, f$) is replaced,
	and that is all.
	$L$ and $R$ changed to texts whose length are both $2f$.
	Hence, the following holds:
	\begin{equation}
		g = 3f+2\cdot 2f+2(1+2f)=11f+2.\label{eq:size1}
	\end{equation}

	Next, we consider $G'$ and how RePair\xspace generates it.
	By its MR-order\xspace,
	$l_1 x$, $\cdots$, $l_f x$, $\mathit{y r_1}$, $\cdots$, $\mathit{y r_f}$
	are replaced before $xy$ is selected.
	They do not overlap with each other, and after they are replaced,
	$xy$ does not occur in the generated text.
	Therefore, in $G'$,
	there are $2f$ rules which derive
	each $\mathit{l_i}x$ and $y\mathit{r_i}$ (for $i = 1, \cdots, f$), respectively,
	but the rule which derives $xy$ is absent.
	$L$ and $R$ changed to texts whose length are both $2f$,
	and $B$ changed to a text with length $2f$.
	Hence, the following holds:
	\begin{equation}
		g' = 2f+2\cdot 2f+2\cdot2f=10f.\label{eq:size2}
	\end{equation}

	Let us denote the length of the original text $T=BL^{f-1}R^{f-1}$ by $n$.
	Then, the following holds:
	\begin{align*}
		n = 4f + 2(3f)(f-1) = 6f^2-2f.~~~
	\end{align*}
	Therefore,
	\begin{align}
		f = \frac{1}{6}(\sqrt{6n+1}+1)\label{eq:length}
	\end{align}
	holds.
	By~(\ref{eq:size1}),~(\ref{eq:size2}),~and~(\ref{eq:length}),
	\begin{align*}
		g - g' &= 11f+2 - 10f = f+2\\
		&=\frac{1}{6}(\sqrt{6n+1}+13)
	\end{align*}

	holds and the theorem follows.

\end{proof}

redpajama_set_name: RedPajamaArXiv


text:
Bay Post-Moruya Examiner's trusted source for property
Fix it Now
Send your results
Place a Bay Post Classifieds Ad
Sponsored content and Magazines
Gift Offers
Editors Pick List
newsletters, editors-pick-list,
A chance decision to join a sewing class in high school led a South Coast business owner to help change the future of people with amputations. Hot n Dry Drysuits owner Charlie Fitzgerald received the Innovative Small Business of the Year award at the Batemans Bay Rotary Club's Pride in Workmanship ceremony last week. He was awarded for his innovative Medi-Dry cover which helps people who have had osseointegration surgery where a prosthesis is fused directly to the bone. This form of surgery leaves an open wound where the metal meets the bone, and the Medi-Dry overcomes a serious problem for amputees. It keeps the skin around the prosthesis protrusion dry and stops the risk of infection from bacteria in water. READ ALSO: How building planes became Broulee man's hobby Mr Fitzgerald and his team invented the cover four years ago when a swimmer contacted the shop and asked if they could help him get back into the pool. "Our motto has always been there's nothing we can't do, so we got to work. It took us about three or four go's to get right," he said. "That customer was able to get back into the pool for the first time since his amputation operation and he's been swimming with it ever since." The Medi-Dry cover is understood to be the only product on the market which keeps the limb completely dry. Mr Fitzgerald said each one is customized perfectly to the person who needs it. "Every single one has to be made to measure because every leg is different and surgeons complete the operation at different places, so it's not one size fits all," he said. The product was modelled after Mr Fitzgerald's neck seal on his own dry suit which allows him to scuba dive and stay bone dry. The biggest Medi-Dry made by the team was for an amputee who completed the Kokoda Track with a cover which protected the man's entire leg from his foot to his groin. "That was a really special one because it meant he could reach his goal of doing the Kokoda and the Medi-Dry kept his prosthesis clean and dry the entire time." Mr Fitzgerald has owned Hot n Dry for five years, but as a keen scuba diver he's been purchasing dry suits from the shop's previous owner for nearly three decades. READ ALSO: Graeme's poppies bloom just in time for Remembrance Day He was a metal worker for most of his life but his career change helped him rediscover skills he had learned on a whim in high school. "Many years ago I decided to join a sewing class in school because I wanted to be in the same class as my girlfriend," he said. "I was the only bloke in a room full of girls but it turned out I really enjoyed it and it's been great to use those skills again making suits for people." It takes about 12 hours for the team to make one Medi-Dry cover after all the measurements have been taken. READ ALSO: South Coast business flourishing on gourmet fairy floss idea Since the first was made four years ago, Mr Fitzgerald has been approached by people all over Australia and the world wanting their own. One of his most memorable customers was a competition swimmer who was back in the pool just two weeks after his amputation operation thanks to Mr Fitzgerald's invention. "We make dry suits for water skiers, scuba divers and even the Australian Antarctic Division team which is a pretty big deal," he said. "But making the Medi-Dry covers is what gives me the most gratitude for my job, to be able to help someone out like that and get them back into doing something they love after their operation."
/images/transform/v1/crop/frm/124793506/28c3e5b1-dc83-4801-9f9a-1014eeeec9cd.JPG/r0_826_3235_2654_w1200_h678_fmax.jpg
November 11 2021 - 12:01PM
Prosthesis cover helps amputees return to the water after surgery
Maeve Bannister
HELPING HAND: Charlie Fitzgerald has made around 40 Medi-Dry covers for amputees all over the world. Photo: Maeve Bannister.
A chance decision to join a sewing class in high school led a South Coast business owner to help change the future of people with amputations.
Hot n Dry Drysuits owner Charlie Fitzgerald received the Innovative Small Business of the Year award at the Batemans Bay Rotary Club's Pride in Workmanship ceremony last week.
He was awarded for his innovative Medi-Dry cover which helps people who have had osseointegration surgery where a prosthesis is fused directly to the bone.
This form of surgery leaves an open wound where the metal meets the bone, and the Medi-Dry overcomes a serious problem for amputees.
It keeps the skin around the prosthesis protrusion dry and stops the risk of infection from bacteria in water.
READ ALSO: How building planes became Broulee man's hobby
Mr Fitzgerald and his team invented the cover four years ago when a swimmer contacted the shop and asked if they could help him get back into the pool.
"Our motto has always been there's nothing we can't do, so we got to work. It took us about three or four go's to get right," he said.
"That customer was able to get back into the pool for the first time since his amputation operation and he's been swimming with it ever since."
The Medi-Dry cover is understood to be the only product on the market which keeps the limb completely dry.
Mr Fitzgerald said each one is customized perfectly to the person who needs it.
"Every single one has to be made to measure because every leg is different and surgeons complete the operation at different places, so it's not one size fits all," he said.
The product was modelled after Mr Fitzgerald's neck seal on his own dry suit which allows him to scuba dive and stay bone dry.
Our motto has always been there's nothing we can't do.
Charlie Fitzgerald
The biggest Medi-Dry made by the team was for an amputee who completed the Kokoda Track with a cover which protected the man's entire leg from his foot to his groin.
"That was a really special one because it meant he could reach his goal of doing the Kokoda and the Medi-Dry kept his prosthesis clean and dry the entire time."
Mr Fitzgerald has owned Hot n Dry for five years, but as a keen scuba diver he's been purchasing dry suits from the shop's previous owner for nearly three decades.
A Medi-Dry cover for a below-knee amputee. Photo: Maeve Bannister.
READ ALSO: Graeme's poppies bloom just in time for Remembrance Day
He was a metal worker for most of his life but his career change helped him rediscover skills he had learned on a whim in high school.
"Many years ago I decided to join a sewing class in school because I wanted to be in the same class as my girlfriend," he said.
"I was the only bloke in a room full of girls but it turned out I really enjoyed it and it's been great to use those skills again making suits for people."
It takes about 12 hours for the team to make one Medi-Dry cover after all the measurements have been taken.
Mr Fitzgerald was recognised for his innovation along with other business owners in a ceremony at the Soldiers Club last week. Front L-R: Myrna from Batemans Bay Soldiers Club, President of Batemans Bay Rotary Club Nicole McDonald, Arkey from Sharp Edges Hairdressing. Back L-R :Chris from Eurobodalla Tippers & Tankers, Charlie Fitzgerald from Hot n Dry Drysuits and Les from the Batemans Bay Historical Society. Photo: Batemans Bay Rotary Club.
READ ALSO: South Coast business flourishing on gourmet fairy floss idea
Since the first was made four years ago, Mr Fitzgerald has been approached by people all over Australia and the world wanting their own.
One of his most memorable customers was a competition swimmer who was back in the pool just two weeks after his amputation operation thanks to Mr Fitzgerald's invention.
"We make dry suits for water skiers, scuba divers and even the Australian Antarctic Division team which is a pretty big deal," he said.
"But making the Medi-Dry covers is what gives me the most gratitude for my job, to be able to help someone out like that and get them back into doing something they love after their operation."
Discuss "South Coast innovation helps amputees get back in the water"
New hospital will be 'magnet' for 'bigger, revitalised' health workforce: Hazzard
Sweeny makes a big jump ahead of exciting 2022 season
Telstra must fix highway blackspots at Termeil and Benadarah says Constance
No double demerits but extra police out in force ahead of Australia Day
Health Minister commits to Level 4 hospital as Labor questions government's statements
Bay Post-Moruya Examiner

redpajama_set_name: RedPajamaCommonCrawl


Our beliefs are summarized in the Ecumenical Creeds and the Three Forms of Unity. The Ecumenical Creeds are shared by all churches worthy of the name Christian. The Three Forms of Unity are three confessions widely used by Reformed churches with roots in the Netherlands.


text:
Trump's Critics Are Letting The Bigger Russia Story Slide
outside your bubble
When meeting an ambassador is a problem, we're in trouble.
By Miriam Elder
Miriam Elder BuzzFeed News World Editor
Posted on March 5, 2017, at 6:33 p.m. ET
Alexander Nemenov / AFP / Getty Images
I lived in Moscow for seven years, from 2006 to 2013, and the current obsession with cataloguing meetings with Russians reminds me of one of the darkest features of Russian politics. And indeed, this focus threatens to turn the biggest story of 2016 — the aggressive and partly open Russian intervention in the US election — into a kind of paranoid partisan meeting tally.
On a winter day almost exactly five years ago, I walked out of my home in central Moscow and stumbled on a surreal scene. Michael McFaul, then two months into his tumultuous stint as US ambassador to Russia, was surrounded by a group of men and women purporting to be from NTV, a state-run TV channel known for taking the lead on hit pieces ordered by the Kremlin.
McFaul was trying to enter the office of Lev Ponomarev, a longtime activist who helped lay the foundation of Russia's human rights advocacy as the Soviet Union crumbled. In the Putin era, he's been physically assaulted and marginalized, but he soldiers on.
"What are you going to talk to Mr Ponomarev about? Why did you come here?" one of the NTV women asks McFaul, in footage later aired on the channel. "We meet often," he replies. As the woman keeps hounding the US ambassador, the exchange becomes more heated: "I was just at the Foreign Ministry! I was meeting with your officials. It's normal!"
"Your ambassador in our country always goes everywhere without all this," McFaul says, in Russian, pointing at the crowd around him. "His work isn't interrupted. But you're always with me — my house. It's interesting. Aren't you embarrassed? It's an insult to your country when you do this."
McFaul suffered for the exchange, but the people he met with really bore the brunt. The Kremlin manufactured a campaign against McFaul from the day he arrived in the country, ensuring that anyone he met was demonized, accused of taking orders from the US State Department. The US ambassador became toxic — by design — so much so that Alexey Navalny, perhaps Russia's leading opposition figure, wouldn't meet with him, or his successor John Tefft, because it would look bad. "The Kremlin press constructed a real hysteria around every meeting with any diplomat," Navalny wrote in an email Saturday.
Fast-forward five years and here we are in the United States, where each meeting with the Russian ambassador is coming under scrutiny. Each day brings new revelations — starting with the news that Attorney General Jeff Sessions failed to disclose two conversations with him during his confirmation hearings, something that raises fair questions about why he would lie.
From there the "revelations" became more suspect. Jared Kushner and Mike Flynn met him, and so did J.D. Gordon and Carter Page. "Russian ambassador Sergey Kislyak leaves trail of U.S. election meddling," read one headline in USA Today. Who didn't meet the Russian ambassador, asked every other person on Twitter.
When meeting an ambassador is a problem, we're in trouble. "It's also strange to me to see so many scandals around meetings with Kislyak — and it's similar to Russia," Navalny said.
And the demonization is spreading beyond Kislyak. On Saturday, Scott Dworkin, co-founder of a group called the Democratic Coalition, tweeted a thread of videos showing Secretary of State Rex Tillerson, then the head of ExxonMobil, meeting Russian President Vladimir Putin and Igor Sechin, one of Putin's closest advisers and, for the past four and a half years, the head of Rosneft, Russia's state-owned oil giant. Dworkin described Sechin and Rosneft as being "from the Dossier." Sechin and Rosneft are indeed mentioned in the dossier, but they are a lot of other things besides — and if you went to Russia to do business in oil, there's a high chance you would come across them. If you were the head of the biggest oil company in the world, as Tillerson was, there was no way to do business in Russia without them.
The real question about contacts between Trump's camp and the Russians, of course, is what they are talking about — what plans they made, whether and how they are coordinating. This is most puzzling in Sessions' case. He says he did not talk about the election with the Russian ambassador in November. What a bizarre admission. Would a US official meeting the Japanese ambassador in February 1942 not discuss Pearl Harbor?
Here is the problem: People inside the Democratic establishment and in the media are looking for a smoking gun, when many of the answers are in plain sight — in the posture of Russian state media, in the WikiLeaks campaign, and beyond. Looking for a secret signal from the Trump camp to Russia to continue the hacking campaign? Why not look instead at Trump's public request in mid-July that Russia hack Clinton's email.
Seventeen US intelligence agencies, and lots of good reporting, said Russia meddled in the US election via its hacks of the DNC and Clinton staffers as well as a disinformation campaign. All but one (the NSA) concluded this was in the service of trying to get Trump elected.
The Russian cyberattack of 2016 was widely documented, but what's happening now is that some of Trump's critics are turning the fabric of diplomacy into conspiracy. They're trying to find evidence that it was his camp that directed those hacks, rather than investigating how they originated in Russia. Of course, it's also important to examine potential ties between Trump, his advisers, and Russia — if for no other reason than no one has yet found a good explanation for Trump's worship of Putin and Russia. But, at the end of the day, it's Russia that hacked the US, in its drive to sow chaos in a country it sees as its rival, and to elect a friendly leader who would both pass amenable policies (like the potential lifting of sanctions) while feeding that very chaos.
Russia pulled off one of the greatest coups in history — and it's getting away with it.
Other perspectives on this story
1 Lots of people argue that the controversy is not over the meetings with Russian officials, but the possible deception about the meetings.
2 Some people argue it is moral equivocation to compare Russian officials and state action with American diplomats.
3 Other people claim that the United States interferes in foreign elections and so the comparison is legitimate.
4 Some people point to the Trump campaign as the origin of focusing scrutiny on meetings with foreign officials.
5 Some people think the emphasis on Russian interference excuses or ignores Clinton's presidential campaign.
"It isn't a fact that anybody meeting with the Russian ambassador is a problem or that such communication is forbidden. But when you are a member of a presidential candidacy and you are communicating with Russia while they are illegally influencing our democratic process, and then lie about it... that's when alarm bells start going off."
user/i_am_bullitt
"False equivalence to compare baseless hysteria around meeting w ambass from our democratic country to legitimate...concerns about myriad connections of Trump team to this backward kleptocracy…Also, let's not pretend that Russia isn't anything other than a corrupt petrostate run by a thug & gang of oligarchs..."
@Millard_Cochki
"US routinely intervenes a hundred to thousand times more egregiously in practically every election on planet."
@ajitrkhegde
"Sorry, but I don't know one critic of Trump that thinks that the problem is the fact that these people met with…the Russian ambassador. The people feeding that line are Pro-Trump supporters using it to say, "see Pelosi did…And Schumer did. Why aren't they being investigated. We are the victims here.""
@mitchellscomet
"Russia's coup was so brilliant it gave Hillary Clinton the popular vote win and managed to make Wisconsin disappear from a map"
@redsteeze
Outside Your Bubble is a BuzzFeed News effort to bring you a diversity of thought and opinion from around the internet. If you don't see your viewpoint represented, contact the curator at bubble@buzzfeed.com. Click here for more on Outside Your Bubble.
Miriam Elder is a political reporter for BuzzFeed News and is based in New York. Her secure PGP fingerprint is 5B5F EC17 C20B C11F 226D 3EBE 6205 F92F AC14 DCB1
Contact Miriam Elder at miriam.elder@buzzfeed.com.


At anytime and anywhere, easy use of cushion typed sun block.
This mild sun cushion is for all skin type, even for sensitive skin.
At the last step of Skin care routine, apply enough amount to the areas where exposed by UV rays.


Red Cannondale Trail SL 4 hardtail stolen from outside the Consulate General of Argentina in Brickell on Thursday (9/20). The bike was locked with a cable lock which was easily cut by the thief. Serial# wsbc602140620f, please contact Pilo if you have any information.


Magnecor lead set for MG Midget and Austin Healey Sprite. High temperature silicone ignition leads with a spiral wound stainless steel core. Design for competition usage or fast road engines. High performance with great reliability.


text:
A Chrome Extension to make it easy to boycott companies.

Initial focus is boycotting companies that use prison labour, but could be expanded to support various campaigns users could opt-in to.

Alpha App[https://chrome.google.com/webstore/detail/easy-boycott/mlcmefgfkgihjoeambhmhbedgiknfokh]

Sources [https://docs.google.com/spreadsheets/d/1qLCwqBs6-7eLP8OL_9B4f5dXTy_QaRRDlpnxPNTC5MQ/edit#gid=0]

## Why Prison Labour?
It is essentially moden day, government endorsed, slavery.
Protected by the dated notion that people convicted of crimes no longer have rights.
As the 13th amendment says: "Neither slavery nor involuntary servitude, *except as punishment for crime*...". I think job training and work experience are incredibly important pieces of rehabilitation and integration, but if someone is doing work they deserve at least minimum wage, not $0.23 - $1.15 [http://money.cnn.com/2012/08/14/smallbusiness/federal-prison-business/].

This app makes it easy to identify and boycott companies that use prison labour, while browsing online.

Atlantic Article [https://www.theatlantic.com/business/archive/2015/09/prison-labor-in-america/406177/]
Netflix Documentary [https://www.youtube.com/watch?v=V66F3WU2CKk]

## Future Features:
- How to best hilight / hide companies?
- Ability to one click tweet/share when you would have bought from a company, but boycott instead due to their use of prison labour.
- Ability to view the full company list from within the app.
- put in app store: https://developer.chrome.com/webstore/publish

## TO Install
- Download the git repo
- open chrome://extensions
- Enable 'developer mode..' at the top of the page
- Select 'load unpacked extension..'
- Select the 'app' folder you downloaded
- Done!

## This app does not reflect the views of any contributors employers. The companies listed are based on best sources avaiable, and we are happy to make any corrections immediately if information is innacurate.

redpajama_set_name: RedPajamaGithub


text:
TV & Film (Movies)
Kermode and Mayo's Film Review
Mark Kermode joins Simon Mayo to give his verdict on the week's movies
Tech Radar Staff • Tech Radar • Sep 1, 2021
"If you're a cinephile, you need to check out Mark Kermode and Simon Mayo's podcast. The podcast brings in plenty of massive celebrities, exhaustive film knowledge and one of the UK's best film critics to make one of the best podcasts about the latest releases."
Alice Florence Orr • PodcastReview.org • Jan 20, 2021
"The best part of the show is their lambasting of terrible movies, although their interviews with actors and directors are also a treat."
More In TV & Film (Movies)
Welcome to the OC, Bitches!
Kast Media, Melinda Clarke, Rachel Bilson
Scream, Queen!
Domino Sound
Pilot TV Podcast
The Empire Podcast
Batman Unburied
Spotify, Warner Bros.


A large wild cat of the feline family (Panthera onca) native to Central and South America. Jaguar cats have tan to orange color skins with black spots along the spine. Their furs were rarely traded but can occasionally be found in rugs.
Encyclopedia Britannica, http://www.britannica.com Comment: "Jaguar." Encyclopædia Britannica. 21 Aug. 2004 .


I had trouble all day and last night with TN, that doesn't stand for Tennessee. It's Trigeminal neualgia, the nerve in my face on the right side causes pain. It usually comes and goes but it has been with me full time today. I hope a good nights sleep will do the trick and I'll be back at the studio tomorrow feeling all better.


text:
Q: How can I add to a List in [InitializeOnLoad] script only once? The problem when using InitializeOnLoad it's invalidating all the time.
Then even if I'm making an instance once for a List at the top of the script it will keep making instance for it all the time and adding more and more items to the List.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using UnityEditor;
using UnityEngine;

[InitializeOnLoad]
public static class CustomHierarchy
{
    private static Vector2 offset = new Vector2(0, 2);
    public static Color gameObjectFontColor = Color.black;
    public static Color prefabOrgFontColor = Color.black;
    public static Color prefabModFontColor = Color.white;
    public static Color inActiveColor = new Color(0.01f, 0.4f, 0.25f);
    public static Color meshRendererColor = Color.yellow;

    public static List<GameObject> gameobjectsHasAll = new List<GameObject>();

    static CustomHierarchy()
    {
        EditorApplication.hierarchyWindowItemOnGUI += HandleHierarchyWindowItemOnGUI;
    }
    private static void HandleHierarchyWindowItemOnGUI(int instanceID, Rect selectionRect)
    {
        Color fontColor = gameObjectFontColor;
        Color backgroundColor = new Color(.76f, .76f, .76f);
        FontStyle styleFont = FontStyle.Normal;
        var obj = EditorUtility.InstanceIDToObject(instanceID);
        GameObject gameObj = EditorUtility.InstanceIDToObject(instanceID) as GameObject;

        if (Selection.instanceIDs.Contains(instanceID))
        {
            backgroundColor = new Color(0.24f, 0.48f, 0.90f);
        }
        if (obj != null)
        {
            var prefabType = PrefabUtility.GetPrefabType(obj);
            if (gameObj.activeInHierarchy == false)
            {
                backgroundColor = inActiveColor;
            }

            if (prefabType == PrefabType.PrefabInstance)
            {
                styleFont = FontStyle.Bold;
                PropertyModification[] prefabMods = PrefabUtility.GetPropertyModifications(obj);
                foreach (PropertyModification prefabMod in prefabMods)
                {
                    if (prefabMod.propertyPath.ToString() != "m_Name" && prefabMod.propertyPath.ToString() != "m_LocalPosition.x" && prefabMod.propertyPath.ToString() != "m_LocalPosition.y" && prefabMod.propertyPath.ToString() != "m_LocalPosition.z" && prefabMod.propertyPath.ToString() != "m_LocalRotation.x" && prefabMod.propertyPath.ToString() != "m_LocalRotation.y" && prefabMod.propertyPath.ToString() != "m_LocalRotation.z" && prefabMod.propertyPath.ToString() != "m_LocalRotation.w" && prefabMod.propertyPath.ToString() != "m_RootOrder" && prefabMod.propertyPath.ToString() != "m_IsActive")
                    {
                        if (HasAllComponents(gameObj, typeof(MeshRenderer), typeof(BoxCollider)))
                        {
                            if (!gameobjectsHasAll.Contains(gameObj))
                                gameobjectsHasAll.Add(gameObj);
                            fontColor = meshRendererColor;
                        }
                        else
                        {
                            fontColor = prefabModFontColor;
                        }

                        break;
                    }
                }
                if (fontColor != prefabModFontColor)
                {
                    if (HasAllComponents(gameObj, typeof(MeshRenderer), typeof(BoxCollider)))
                    {
                        gameobjectsHasAll.Add(gameObj);
                        fontColor = meshRendererColor;
                    }
                    else
                    {
                        fontColor = prefabOrgFontColor;
                    }
                }
            }
            else
            {
                if (HasAllComponents(gameObj, typeof(MeshRenderer), typeof(BoxCollider)))
                {
                    gameobjectsHasAll.Add(gameObj);
                    fontColor = meshRendererColor;
                }
            }
            Rect offsetRect = new Rect(selectionRect.position + offset, selectionRect.size);
            EditorGUI.DrawRect(selectionRect, backgroundColor);
            EditorGUI.LabelField(offsetRect, obj.name, new GUIStyle()
            {
                normal = new GUIStyleState() { textColor = fontColor },
                fontStyle = styleFont
            }
            );
        }
    }

    public static bool HasAllComponents(GameObject gameObject, params System.Type[] types)
    {
        for (int i = 0; i < types.Length; i++)
        {
            if (gameObject.GetComponent(types[i]) == null)
                return false;
        }

        return true;
    }
}

The List variable is:
public static List<GameObject> gameobjectsHasAll = new List<GameObject>();

And I'm adding objects to the list in 3 places in the code in each place where HasAllComponents is true for example:
if (HasAllComponents(gameObj, typeof(MeshRenderer), typeof(BoxCollider)))
                    {
                        gameobjectsHasAll.Add(gameObj);
                        fontColor = meshRendererColor;
                    }

In the Hierarchy I have 6 items that meet the HasAllComponents condition.
But at the first time the List contain 36 items it keep adding the 6 items 6 times.
Then next 120 items or so and it keep adding the same items nonstop.
I'm calling this List from another script EditorWindow script:
using System;
using UnityEditor;
using UnityEngine;
using System.Collections;
using System.Reflection;
using System.Linq;
using System.Collections.Generic;

public class HierarchyEditor : EditorWindow
{
    public static bool multipleComponents = false;
    public static string multipleComponentsString = "";

    private static SearchableEditorWindow hierarchy { get; set; }
    private string filterText = "";
    private string oldFilterText = "";

    [MenuItem("Tools/Hierarchy Editor")]
    public static void ShowWindow()
    {
        GetWindow<HierarchyEditor>("HierarchyEditor");

        Test();
    }

Where Test is:
private static void Test()
    {
        var all = CustomHierarchy.gameobjectsHasAll;
    }

A: Before all of the lines
gameobjectsHasAll.Add(gameObj);

check if the object is already in the list and only  add it if it is not there yet
if(!gameobjectsHasAll.Contains(gameObj))
{
    gameobjectsHasAll.Add(gameObj);
    fontColor = meshRendererColor;
}

so far it seems that you check this only once.

A: I believe you need to process only one element inside your HandleHierarchyWindowItemOnGUI method as you assign it to EditorApplication.hierarchyWindowItemOnGUI delegate. Manual says "Delegate for OnGUI events for every visible list item in the HierarchyWindow." (https://docs.unity3d.com/ScriptReference/EditorApplication-hierarchyWindowItemOnGUI.html), so for each list element (you have 6) it call it for each element again. And here is unity live cycle (https://docs.unity3d.com/Manual/ExecutionOrder.html), you see it continuously calling OnGUI(), so as you list is static instance of cause it does not remove previous objects from it, and as OnGUI() processing list and create new instances which pass through your check, list will grow and grow.
So you may want to clear list inside you HandleHierarchyWindowItemOnGUI method, before processing it again.

redpajama_set_name: RedPajamaStackExchange