|Deletions are marked like this.||Additions are marked like this.|
|Line 23:||Line 23:|
|. = leftMunch lrsp -- longest right-Skew prefix = rightMunch llds = rightMunch lrss|| . = leftMunch lrsp -- longest right-Skew prefix
. = rightMunch llds
. = rightMunch lrss
2008 M Term Week 3
Presenter : Sharon Curtis
Sharon presented a solution to the maximum-density segment problem with decreasing right-skew partition (DRSP).
Density is defined as the total area of a sequence of items over the total width. In a DRSP, the density of each segment must be strictly decreasing and each segment must be right-skew (defined below)
forall u,v st. y = u++v => density u <= density v
The four ways that computes the unique DRSP is
drsp :: [Item] -> Item
drsp x = leftMunch lhdp - longest highest-density prefix
- = leftMunch lrsp -- longest right-Skew prefix
- = rightMunch llds
- = rightMunch lrss
leftMunch :: ([Item] -> [Item]) -> [Item] -> Item
leftMunch m  = 
leftMunch m x = y : leftMunch (drop (#y) x)
- where y = m x
Consider the maximum-density segment with a minimum length l.
The solution is to start with a suffix (window) of the sequence and take away the first l elements. The rest of the suffix is DRSPed. It is then checked segment by segment to append to the first l elements.
After this step, the remaining window (first l element + the chosen segments) is shifted leftwards by consing one element to the left. As a result, the first l compulsory elements are also shifted leftward and the DRSP of the remaining list is updated with one more element to the left.
This update is easy given the following property
tail (drsp (x:xs)) is a suffix of drsp xs
To implement this update, the sequence is represented as a tree.
DTree a = Node a [DTree a]
makeDTree (i,is) = Node i (map makeDTree (drsp is))
Ralf's comment here:
Density does not play a part here. It is all about partition properties,
which is orthogonal and more general.
This algorithm can be generalized with maximum-density segment with both a minimum length and a maximum length.
In general, it is needed to split a tree. It is again down to reDRSP it with a suffix dropped.
Jeremy and Geraint's proof of
density x <= density y and rightSkew x and rightSkew y implies rightSkew (x++y)
density x1 <= density (x1++x2++y) <= density (x2++y)
What is this wiki about?
Interesting starting points:
RecentChanges: see where people are currently working
WikiSandBox: feel free to change this page and experiment with editing
FindPage: search or browse the database in various ways
SyntaxReference: quick access to wiki syntax
SiteNavigation: get an overview over this site and what it contains
How to use this site
A Wiki is a collaborative site, anyone can contribute and share:
Edit any page by pressing Edit at the top or the bottom of the page
Create a link to another page with joined capitalized words (like WikiSandBox) or with [[words in brackets]]
- Search for page titles or text within pages using the search box at the top of any page
This wiki is powered by MoinMoin.