§11.2
Buildingaconcordanceforatextle 199
11.2 Buildingaconcordanceforatextle
Thisexamplebuildsandprints aconcordancefroma textle: : for r everywordin
theleitndsthelinenumbersonwhichthewordoccurs. Theexampleisinle
Fileindex.cs
. Wecanuseadictionarytomapeachwordtoasetofthenumbers
oflinesonwhichitoccurs;asetavoidsduplicatelinenumbersforeachword.The
dictionary isa treedictionary tomakesurethewordscomeout sortedwhenthe
dictionary is printed,andtheset ofline numbersis a treeset tomakesurethe
linenumbers foreachwordaresorted. . Foreach h wordthelinenumbersarerep-
resentedbyaTreeSet<
int
>,andhencetheentireconcordanceisrepresentedbya
TreeDictionary<String,TreeSet<
int
>>.
Method
IndexFile
buildstheconcordanceforagivenlename:
static IDictionary<String, TreeSet<int>> > IndexFile(String g filename) {
IDictionary<String, TreeSet<int>> > index
= new w TreeDictionary<String, TreeSet<int>>();
Regex delim = new w Regex("[^a-zA-Z0-9]+");
using (TextReader r rd d = new StreamReader(filename)) ) {
int lineno = 0;
for (String line e = = rd.ReadLine(); line e != = null; ; line e = rd.ReadLine()) ) {
String[] res = = delim.Split(line);
lineno++;
foreach (String g s s in res)
if (s != "") ) {
if (!index.Contains(s))
index[s] = = new TreeSet<int>();
index[s].Add(lineno);
}
}
}
return index;
}
Insteadofatreedictionary,onemighthaveusedahashdictionaryandthensortthe
entriesbeforeprintingthem.Insteadofatreesetoflinenumbersonemighthave
usedalist(becausethelinesarescannedinorderofincreasinglinenumbersany-
way)andeithereliminateduplicatesafterwards(seepattern80),oruseahashed
(arrayorlinked)listtoavoidduplicatedduringtheconstruction.Itisnotclearthat
thesealternativeswouldhavebeenanymoreefcient.Usingatreedictionaryand
treesetsnaturallyachievestheabsenceofduplicates,andtheresult
index
returned
bymethod
IndexFile
abovewillprintinalphabeticalorderwithoutfurtherado:
foreach (String word d in n index.Keys) {
Console.Write("{0}: ", , word);
foreach (int t ln in n index[word])
Console.Write("{0} ", , ln);
Console.WriteLine();
}
Pdf change font size - Compress reduce PDF size in C#.net, ASP.NET, MVC, Ajax, WinForms, WPF
C# Code & .NET API to Compress & Decompress PDF Document
reduce pdf file size; adjust pdf size preview
Pdf change font size - VB.NET PDF File Compress Library: Compress reduce PDF size in vb.net, ASP.NET, MVC, Ajax, WinForms, WPF
VB.NET PDF Document Compression and Decompression Control SDK
change page size of pdf document; adjust size of pdf file
200 Convexhullintheplane
§11.3
11.3 Convexhullintheplane
Theconvexhullistheleastconvexsetthatenclosesagivensetofpoints.Apointset
isconvexifeverypointbetweentopointsthatbelongtothesetalsobelongstothe
set:thesethasnoholesorinwarddents.Figure11.1showsanexampleofseveral
pointsandtheirconvexhull,enclosedbyasolidline.
right
left
Figure11.1:Apointsetanditsconvexhullintheplane.
Graham’salgorithm[16]fornding theconvexhull in theplane, as modiedby
Andrew[2],consistsoffoursteps,implementedinle
GConvexHull.cs
:
1. Sortthepointslexicographicallybyincreasing(x;y),thusndingalsoaleft-
most point
left
anda rightmostpoint
right
. Severalpointsmay y havethe
sameminimalormaximalxcoordinate;anysuchpointwilldo.
2. Partitionthepoint t setintotwolists,
upper
and
lower
, accordingaspointis
aboveorbelowthelinesegmentfrom
left
to
right
,shownbyadottedlinein
gure11.1. Theupperlistbeginswithpoint
left
andendswith
right
;the
lowerlistbeginswithpoint
right
andendswith
left
.
3. Traversethepointlistsclockwise,eliminatingallbuttheextremepoints(thus
eliminatingalsoduplicatepoints).ThisisGraham’spointeliminationscan.
4. Jointhepointlists(inclockwiseorder)inanarray,leavingoutpoint
left
from
the
lower
listandpoint
right
fromthe
upper
list.
UsingC5,thesestepscanbeimplementedasfollows:
// 1. Sort points s lexicographically y by increasing g (x, , y)
int N = = pts.Length;
Array.Sort(pts);
Point left = pts[0], right = = pts[N N - 1];
// 2. Partition into lower hull and upper hull
IList<Point> lower r = = new LinkedList<Point>(),
upper = = new LinkedList<Point>();
lower.InsertFirst(left); upper.InsertLast(left);
C# PDF insert text Library: insert text into PDF content in C#.net
Powerful .NET PDF edit control allows modify existing scanned PDF text. Ability to change text font, color, size and location and output a new PDF document.
change font size pdf form reader; reader shrink pdf
C# PDF Annotate Library: Draw, edit PDF annotation, markups in C#.
Able to edit and change PDF annotation properties such as font size or color. Abilities to draw markups on PDF document or stamp on PDF file.
pdf paper size; change font size in pdf
§11.4
Convexhullintheplane 201
for (int i i = = 0; i < < N; ; i++) {
double det t = Point.Area2(left, , right, , pts[i]);
if (det t < < 0)
lower.InsertFirst(pts[i]);
else if f (det t > 0)
upper.InsertLast(pts[i]);
}
lower.InsertFirst(right);
upper.InsertLast(right);
// 3. Eliminate points not on n the e hull
Eliminate(lower);
Eliminate(upper);
// 4. Join n the e lower r and d upper r hull, , leaving out lower.Last and d upper.Last
Point[] res = new Point[lower.Count + upper.Count - - 2];
lower[0, lower.Count t - - 1].CopyTo(res, 0);
upper[0, upper.Count t - - 1].CopyTo(res, lower.Count - - 1);
Graham’spointeliminationscan,whichisstep(3)above,worksasfollows:
 Considerthreeconsecutivepointsp
0
;p
1
;p
2
.
 Iftheymakearightturn,then p
1
isnotintheconvexsetspannedbyp
0
,p
2
andotherpoints;keepit.
 Otherwiseeliminatep
1
andgobacktoreconsiderp
0
.
UsingC5listviews,itcanbeimplementedasfollows:
public static void Eliminate(IList<Point> > list) ) {
IList<Point> view w = = list.View(0, 0);
int slide e = = 0;
while (view.TrySlide(slide, , 3))
if (Point.Area2(view[0], view[1], view[2]) < 0)
// right t turn
slide = 1;
else {
// left t or r straight
view.RemoveAt(1);
slide = view.Offset != 0 0 ? ? -1 : 0;
}
}
}
Ineveryiterationofthe
while
loop,the
view
focusesonthreeconsecutivepoints.If
theyformarightturn,slide
view
totheright(by1);elseremovethemiddlepoint,
andslide
view
totheleft(by 1)unlessatthebeginningofthelist.
All the e aboveoperations, including
RemoveAt(1)
, areefcient t when
list
is a
linked list, and considerablyclearerthan implementations s using explicit manip-
ulationoflinkedlistnodes.Alsonotethatthepointdeletionoperation
RemoveAt(1)
cannotbeefcientlyimplementedwhenusingarraylists.
C# PDF Sticky Note Library: add, delete, update PDF note in C#.net
Allow users to add comments online in ASPX webpage. Able to change font size in PDF comment box. Able to save and print sticky notes in PDF file.
batch pdf compression; .pdf printing in thumbnail size
C# PDF Convert to Word SDK: Convert PDF to Word library in C#.net
PDF document, keeps the elements (like images, tables and chats) of original PDF file and maintains the original text style (including font, size, color, links
change font size in pdf text box; change paper size in pdf
202 Findinganagramclasses
§11.4
11.4 Findinganagramclasses
Twowords areanagrams ofeachotherifonecan beobtained d from theother by
rearranging its letters. . Forinstance e generate  andteenager areanagrams of
eachother.Fromacollectionpointofview,twowordsareanagramsofeachotherif
theycontainthesamebagofletters. Fortheaboveexample,thisbagis{a,e,e,e,
g,n,r,t}.
Clearly,acollectionofwordscanbedividedintodisjointanagramclassessuch
anytwowordsinananagramclassareanagramsofeachother,andnotwowords
fromdifferent anagramclassesareanagrams ofeachother. . Eachanagramclass
ischaracterizedbyabagofletters (characters). . Ananagram m classistrivialifit
containsonlyoneword.Thisexampleisinle
Anagrams.cs
.
Considerthefollowingtask: Divideagivenwordlistintoanagramclasses,for
eachnon-trivial anagramclass,printthewordsit contains. . Thewordlistispre-
sentedasanenumerableofstringsandmaycontainduplicates.
Given a word(string)wecan nd its anagram class (as a bag of f characters)
straightforwardlylikethis:
public static HashBag<char> AnagramClass(String s) ) {
HashBag<char> anagram = new w HashBag<char>();
foreach (char r c c in n s)
anagram.Add(c);
return anagram;
}
Thedefaultitemequalitycomparerusedbythe
anagram
hashbagisCharEquali-
tyComparer;seesection2.3. Tomanagetheanagramclassesandthewordsthat
belongtothem,weusea dictionarythatmapsananagramclasstothesetofthe
wordsinthatclass. Thenwesimplygothroughthegivenwordlist,ndtheana-
gramclassofeachword,andcheckwhetherwehaveseenthatanagramclassbefore,
andifnot,createanewentryforthatanagramclassinthedictionaryandassociate
itwithanewemptysetofwords.Thenaddthewordtothesetassociatedwithits
anagramclass.
Generate Barcodes in Web Image Viewer| Online Tutorials
Change Barcode Properties. Select "Font" to choose human-readable text font style, color, size RasterEdge OCR Engine; PDF Reading; Encode & Decode JBIG 2 Files;
change font size in pdf form field; change page size pdf
C# PDF Field Edit Library: insert, delete, update pdf form field
Able to add text field to specified PDF file position in C#.NET class. Support to change font size in PDF form. Able to delete form fields from adobe PDF file.
pdf page size dimensions; adjust file size of pdf
§11.4
Findinganagramclasses 203
Method
AnagramClasses
below takes s as argument t a a stream of words s and d re-
turnsastreamofthenon-trivial anagramclasses,eachbeing astreamofwords.
Astreamis representedasanenumerable e oftypeSCG.IEnumerable<T>,where
SCGabbreviatestheSystem.Collections.Genericnamespace. Thevariable
classes
holdstheanagramclassesfoundsofarandhastypeIDictionary<HashBag<
char
>,
TreeSet<String>>.
public static SCG.IEnumerable<SCG.IEnumerable<String>>
AnagramClasses(SCG.IEnumerable<String> ss)
{
IDictionary<HashBag<char>, TreeSet<String>> classes
= new w HashDictionary<HashBag<char>, , TreeSet<String>>();
foreach (String g s s in n ss) {
HashBag<char> anagram = AnagramClass(s);
TreeSet<String> anagramClass;
if (!classes.Find(anagram, , out t anagramClass))
classes[anagram] = = anagramClass = new TreeSet<String>();
anagramClass.Add(s);
}
foreach (TreeSet<String> > anagramClass in classes.Values)
if (anagramClass.Count > 1)
yield return anagramClass;
}
Notethatweusecollectiontypesbothforthekeytype(HashBag<
char
>)andthe
valuetype(TreeSet<String>)inthedictionary. Inparticular,theHashBag<
char
>
keyitemsmust becomparedbycontents: : twobags s areequal ifthey containthe
samecharacterswith thesamemultiplicity. . Thekey y equality comparer usedby
the
classes
hashdictionaryisthedefaultequalitycomparerforthekeytypeHash-
Bag<
char
>:anunsequencedcollectionequalitycomparer;seesection2.3.
Thewordsofeachnon-trivialanagramclassfoundbymethod
AnagramClasses(ss)
canbeprinted,oneanagramclassperline,asshownbelow. Theparameter
ss
has
typeSCG.IEnumerable<String>:
foreach (SCG.IEnumerable<String> > anagramClass s in AnagramClasses(ss)) {
foreach (String g s s in n anagramClass)
Console.Write(s + + " ");
Console.WriteLine();
}
Theanagramclass problemcouldalsobesolvedby using aTreeBag<
char
>any-
where a a HashBag<
char
> is usedabove. . This s solution n has similar efciency for
medium-sizeproblems(100000anagramclasses,ofwhich10000non-trivial),but
usesslightlymorememoryandsoissloweronsystemsthatdonothavesufcient
RAM.
VB.NET Image: Visual Basic .NET Guide to Draw Text on Image in .
Please note that you can change some of the LoadImage) Dim DrawFont As New Font("Arial", 16 provide powerful & profession imaging controls, PDF document, image
pdf compression; optimize scanned pdf
C# Image: Use C# Class to Insert Callout Annotation on Images
including GIF, PNG, BMP, JPEG, TIFF, PDF & Word projects; Easy to set annotation filled font property individually an easy way; C# demo code to change the filled
best pdf compressor; change paper size pdf
204 Finiteautomata
§11.5
11.5 Finiteautomata
Thisexampleshowshowtousesets,dictionariesandqueuesfromtheC5library
tosystematicallyconstructadeterministicniteautomatonfromagivennondeter-
ministicniteautomaton.Theexampleisinle
GNfaToDfa.cs
.
Anondeterministicniteautomaton(NFA)isadirectedgraph,asshowning-
ure11.2,withstatesshownasovals,andtransitionsshownasarrowsfromonestate
toanother. Atransitionislabelledwithaletterorwiththespecialsymbolepsilon
(e),writtenepsinthegure.AnNFAhasasinglestartstateandoneormoreaccept
states,thelattershownasdoubleovals.
start
d6
d4
eps
d7
eps
d10
d0
d1
A
d5
eps
d3
eps
eps
eps
d2
eps
d8
A
d9
B
B
eps
Figure11.2:Anondeterministicniteautomatonfor(AjB)AB.
AnondeterministicniteautomatonissaidtorecognizeastringsuchasAAABAB
ifthereisasequenceoftransitionsfromthestartstatetoanacceptstate,suchthat
theconcatenationofthetransitions’labelsequalsthestring,ignoringepsilons.The
NFAingure11.2recognizesthestringsAB,AAB,BAB,andinnitelymanyothers;
infact,exactlythosestringsofA’sandB’sthatendinAB.Ontheotherhand,itdoes
notrecognizethestringsAAAorBAorBorA.
deterministicniteautomaton (DFA)isan NFAthatsatises: : (1)no o state
has more e than one transition with thesame label, and (2)thereareno epsilon
transitions.Figure11.3givesanexampleDFA.
start
d1
d0
A
d2
B
d3
A
B
B
A
A
B
Figure11.3:AdeterministicniteautomatonequivalenttotheNFAingure11.2.
FromanyNFAonecansystematicallyconstructanequivalentDFA;infactthe
DFAingure11.3hasbeenconstructedfromtheNFAingure11.2.Thisconstruc-
tionisusefulbecausethereisasimplewaytomakeanNFAfromagivenregular
§11.5
Finiteautomata 205
expression,andthereisanefcientwaytocheckwhetheraDFArecognizesagiven
string. Together, , thisgives an efcient t way tocheckwhethera particularstring
matchesagivenregularexpression.
Anondeterministicniteautomatoncanberepresentedbyastartstate,anac-
ceptancestate(onlyoneforsimplicity),anditstransitionrelation:adictionarythat
mapsastate(an
int
)toanarraylistofTransitions,whereaTransitionisapair
ofalabel
lab
anda
target
state. Alabelisastring,andweusethelabel
null
to
denoteepsilontransitions.
class Nfa a {
private readonly y int startState;
private readonly y int exitState;
// This is the e unique e accept state
private readonly y IDictionary<int, ArrayList<Transition>> trans;
...
}
public class Transition {
public readonly y String lab;
public readonly y int target;
public Transition(String g lab, , int t target) {
this.lab = lab; ; this.target = = target;
}
}
Givenanondeterministicniteautomaton(NFA)wecanconstructadeterministic
niteautomaton(DFA)intwomainsteps:
1. ConstructaDFAeachofwhosestatesiscomposite,namelyasetofNFAstates.
Thisisdonebymethods
CompositeDfaTrans
and
EpsilonClose
below.
2. Replaceeachcompositestate(a a Set<
int
>)bya simplestate(an
int
). This
isdoneby method
MkRenamer
,whichcreatesa renamer,andmethod
Rename
,
whichappliestherenamertothecomposite-stateDFAcreatedinstep1.
Theabovestepscanbeimplementedasfollows:
// 1. Construct composite-state e DFA
IDictionary<Set<int>, IDictionary<String, Set<int>>>
cDfaTrans = = CompositeDfaTrans(startState, , trans);
// 2. Replace composite states s with h simple e (int) ) states
ICollectionValue<Set<int>> cDfaStates = cDfaTrans.Keys;
IDictionary<Set<int>, int> > renamer = MkRenamer(cDfaStates);
IDictionary<int, IDictionary<String, int>> > simpleDfaTrans s =
Rename(renamer, cDfaTrans);
206 Finiteautomata
§11.5
Method
EpsilonClose
,shownbelow,computesandreturnstheepsilon-closureof
agivenNFAstate
s
,thatis,thesetofallNFAstatesthatarereachablefrom
s
by
epsilontransitions. Thisisdoneasfollows:Letaset
S
ofstatesbegiven. Putthe
statesof
S
onaworklist.Repeatedlychooseandremoveastate
s
fromtheworklist,
andconsider all epsilon-transitions
s
e
!
s’
from
s
tosomestate
s’
. If
s’
isin
S
already,thendonothing; otherwiseadd
s’
to
S
andtotheworklist. Whenthe
worklistisempty,
S
isepsilon-closed;return
S
.
static Set<int>
EpsilonClose(Set<int> S, IDictionary<int, ArrayList<Transition>> trans) {
// The e worklist initially y contains all l S S members
IQueue<int> worklist = new w CircularQueue<int>();
S.Apply(worklist.Enqueue);
Set<int> res = new Set<int>(S);
while (!worklist.IsEmpty) ) {
int s s = worklist.Dequeue();
foreach (Transition tr in n trans[s]) {
if (tr.lab b == null && & !res.Contains(tr.target)) {
res.Add(tr.target);
worklist.Enqueue(tr.target);
}
}
}
return res;
}
Method
CompositeDfaTrans
,shownbelow,buildsandreturnsthetransitionrelation
ofacomposite-stateDFAequivalenttotransitionrelationofthegivenNFA.Thisis
doneasfollows:Createtheepsilon-closure
S0
(aSet<
int
>)oftheNFA’sstartstate
s0
,andputitinaworklist(anIQueue<Set<
int
>>).CreateanemptyDFAtransition
relation
res
,whichisadictionarythatmapsacompositestate(anepsilon-closedset
of
int
s)toadictionarythatmapsalabel(anon-nullstring)toacompositestate.
Repeatedlychooseacompositestate
S
fromtheworklist.If
S
isnotalreadyinthe
keysetoftheDFAtransitionrelation,computeforeverynon-epsilonlabel
lab
the
set
T
ofstatesreachablebythatlabelfromsomestate
s
in
S
.Computetheepsilon-
closure
Tclose
ofeverysuchstate
T
andputitontheworklist. Thenforevery
lab
,
addthetransition
S
lab
!
Tclose
totheDFAtransitionrelation.
§11.5
Finiteautomata 207
static IDictionary<Set<int>, IDictionary<String, Set<int>>>
CompositeDfaTrans(int s0, , IDictionary<int, , ArrayList<Transition>> > trans) ) {
Set<int> S0 0 = EpsilonClose(new w Set<int>(s0), , trans);
IQueue<Set<int>> worklist = = new w CircularQueue<Set<int>>();
worklist.Enqueue(S0);
// The e transition relation n of f the e DFA
IDictionary<Set<int>, IDictionary<String, Set<int>>> > res =
new HashDictionary<Set<int>, , IDictionary<String, Set<int>>>();
while (!worklist.IsEmpty) {
Set<int> S = worklist.Dequeue();
if (!res.Contains(S)) {
// The e S -lab-> > T T transition relation being constructed for a given n S
IDictionary<String, Set<int>> STrans s =
new HashDictionary<String, , Set<int>>();
// For r all s in S, consider all transitions s s -lab-> > t
foreach (int s s in n S) {
// For all non-epsilon n transitions s s -lab-> > t, , add t to o T
foreach (Transition tr r in n trans[s]) ) {
if (tr.lab b != = null) ) {
// Non-epsilon transition
Set<int> toState;
if (STrans.Contains(tr.lab))
// Already y a a transition on lab
toState = = STrans[tr.lab];
else {
// No transitions on n lab b yet
toState = = new Set<int>();
STrans.Add(tr.lab, toState);
}
toState.Add(tr.target);
}
}
}
// Epsilon-close all l T such that S S -lab-> > T, and put on worklist
IDictionary<String, Set<int>> STransClosed =
new HashDictionary<String, , Set<int>>();
foreach (KeyValuePair<String, Set<int>> entry y in n STrans) ) {
Set<int> Tclose = EpsilonClose(entry.Value, , trans);
STransClosed.Add(entry.Key, Tclose);
worklist.Enqueue(Tclose);
}
res.Add(S, STransClosed);
}
}
return res;
}
208 Finiteautomata
§11.5
Method
MkRenamer
,shownbelow, creates and returnsa a renamer, , a a dictionary
thatmapsSet<
int
>to
int
. Thisisdoneasfollows:GivenacollectionofSet<
int
>,
createanew injectivedictionary that mapsfrom Set<
int
> to
int
, by choosing a
fresh
int
foreverykeyinthegivendictionary.ThecollectionofSet<
int
>isactually
thekeysetofthecomposite-stateDFA’stransitionrelation,ascomputedbymethod
CompositeDfaTrans
above.
static IDictionary<Set<int>, , int> > MkRenamer(ICollectionValue<Set<int>> > states) ) {
IDictionary<Set<int>, int> > renamer r = new HashDictionary<Set<int>, int>();
int count = 0;
foreach (Set<int> k k in states)
renamer.Add(k, count++);
return renamer;
}
Method
Rename
,shownbelow,createsandreturnsa DFAwhosestatesaresimple
int
s.Thisisdoneasfollows:Givenarenamerasconstructedbymethod
MkRenamer
,
andgiventhecomposite-stateDFA’stransition relation,createandreturn anew
transitionrelationasadictionaryinwhicheverySet<
int
>hasbeenreplacedbyan
int
,asdictatedbytherenamer.
static IDictionary<int, IDictionary<String, , int>>
Rename(IDictionary<Set<int>, int> > renamer,
IDictionary<Set<int>, IDictionary<String, Set<int>>> trans)
{
IDictionary<int, IDictionary<String, , int>> newtrans =
new HashDictionary<int, , IDictionary<String, int>>();
foreach (KeyValuePair<Set<int>, IDictionary<String, Set<int>>> > entry
in trans) ) {
Set<int> k = entry.Key;
IDictionary<String, int> > newktrans s = = new w HashDictionary<String, int>();
foreach (KeyValuePair<String, Set<int>> tr in n entry.Value)
newktrans.Add(tr.Key, renamer[tr.Value]);
newtrans.Add(renamer[k], newktrans);
}
return newtrans;
}
Documents you may be interested
Documents you may be interested