Represent an element in a free monoid with minimum weight

Consider a rank $k$ free monoid $(M, \cdot)$ with free generators $G$ . Sometimes there are ways to express them by writing a little less than write the whole string of generators. We can group some generators by powers. For example, $aababababaaaa = a (ab)^{4} a^{4}$ .

Problem1

Find the shortest way to write down an element in a free monoid.

There are problems on how long are the parentheses, exponents etc. Therefore we generalize it to allow weight to those operations.

Formally. For any free monoid $M$ with free generators $G$ , we can construct another free monoid $(M^{*}, \cdot)$ ,

$a \in G ⟹ A t o m (a) \in M^{*}$ .
$a \in M^{*}$ , $n \in N$ , then $P o w er (a, n) \in M^{*}$ .

Definition2

Consider a homomorphism $w : M^{*} \to N$ . Such that for all $n$ , it satisfy the following criteria:

$w (a) \leq w (b) ⟹ w (P o w er (a, n)) \leq w (P o w er (b, n))$ ,
$w (a) \leq w (P o w er (a, 1))$ .

$w$ is a weight function.

Let $f : M^{*} \to M$ , such that

$f (ab) = f (a) f (b)$ ,
$f (A t o m (a)) = a$ ,
$f (P o w er (a, n)) = a^{n}$ .

Problem3

Given $a \in M$ , we want to find $a^{'} \in M^{*}$ , such that $f (a^{'}) = a$ and $w (a^{'})$ is minimized.

The input is $a_{1} \dots a_{n}$ .

Let $D (i, j)$ represent the minimum weight representation for $a_{i} \dots a_{j}$ . Let $P (i, j)$ represent the set of all possible $P o w er (x, k)$ , such that $f (P o w er (x, k)) = a_{i} \dots a_{j}$ for some $k \neq = 1$ .

$D (i, i) D (i, j) = a_{i} = min (P (i, j) \cup {D (i, k) + D (k + 1, j) ∣ i \leq k \leq j - 1})$

Here $min$ return any of the expressions that achieves the minimum weight. This allows a $O (n^{3})$ algorithm if one uses suffix tree for finding $P (i, j)$ . One can naively try all possible $P o w er (x, k)$ instead, where $k ∣ n$ .

Here is an Haskell code for it. It is designed to show the algorithm instead of been efficient. This has real life usage to compress regular expressions.

	{-# LANGUAGE RankNTypes #-}
	module FreeMonoidCompress (Exp(Atom,List,Power), freeMonoidCompress, latexWeight) where
	import Data.List
	import Data.Array
	import qualified Math.NumberTheory.Primes.Factorisation as F
	import Data.List.Split
	import Data.Set (toAscList)
	-- The idea is we are working over a free monoid. There is a function l for individual
	-- generators, and there is a l', such that l' [a] = l a

	data Exp a = Atom a \| List [Exp a] \| Power (Exp a) Int
	deriving (Eq, Ord)-- ,Show)
	list :: forall a. Exp a -> Exp a -> Exp a
	list (List xs) (List ys) = List (xs++ys)
	list (List xs) y = List (xs++[y])
	list x (List ys) = List (x:ys)
	list x y = List [x,y]

	instance (Show a) => Show (Exp a) where
	show (List xs) = concatMap show xs
	show (Power x n) = base ++ "^" ++ exp
	where base
	\| isatom x = show x
	\| otherwise = "("++show x++")"
	exp
	\| length (show n) == 1 = show n
	\| otherwise = "{"++show n++"}"
	isatom (Atom x) = True
	isatom _ = False
	show (Atom x) = show x

	-- example length
	latexWeight :: Exp Char->Integer
	latexWeight (Atom _) = 1
	latexWeight (List xs) = sum $ map latexWeight xs
	latexWeight (Power ea n) = min (latexWeight $ List (replicate n ea)) (overhead1 + 1 + overhead2 + toInteger (length $ show n) + w)
	where w = latexWeight ea
	overhead2 = if 1 == length (show n) then 0 else 2
	overhead1 = if w == 1 then 0 else 2

	freeMonoidCompress :: forall a e.
	(Ord a, Ord e) =>
	(Exp e -> a) -> [e] -> Exp e
	--(Exp e -> a) -> [e] -> (a, Exp e)
	--w is the weight
	freeMonoidCompress w m = snd $ f 0 n --b!(0,n-1)
	where b = array ((0,0),(n,n)) [((x,y), snd (f x y))\|x<-[0..n],y<-[0..n]] --stores solution
	n = length m - 1
	f i j
	\| i == j = (w (Atom (m!!i)), Atom (m!!i))
	\| otherwise = (bv,bm)
	where (bv,bm) = minimum $ powers ++ [part k\| k<-[i..j-1]]
	part k = (w sol, sol)
	where sol = list (b!(i,k)) (b!(k+1,j))
	powers = [(w (v k), v k) \| k <- divisors l, isPower (chunksOf k xs), k /= l]
	where xs = [m!!t\|t<-[i..j]]
	l = j-i+1
	v k = Power (b!(i,i+k-1)) (l `div` k)
	isPower p = all (==head p) p

	divisors :: Int -> [Int]
	divisors = map fromInteger . toAscList . F.divisors . fromIntegral

view raw FreeMonoidCompress.hs hosted with ❤ by GitHub

Posted by Chao Xu on 2013-03-26.

Tags: Haskell, monoid.