NAME

Lingua::LTS::Trie - native perl deterministic prefix tree map

(Back to Top)

SYNOPSIS

 ##========================================================================
 ## PRELIMINARIES

 use Lingua::LTS::Trie;

 ##========================================================================
 ## Constructors etc.

 $obj   = CLASS_OR_OBJ->new(%args);     ##-- new trie
 $trie2 = $trie->clone;                 ##-- copy of existing trie

 ##========================================================================
 ## Methods: Construction

 $qid = $trie->add($str,$val);          ##-- add a mapping (character-wise)
 $qid = $trie->addArray(\@syms,$val);   ##-- add a mapping (element-wise)
 undef = $trie->remove($str);           ##-- remove a mapping (dangerous)

 ##========================================================================
 ## Methods: Output packing

 $trie = $trie->packout(%args);         ##-- utility for pseudo-set outputs

 ##========================================================================
 ## Methods: Lookup

 $q = $trie->s2q($str);                 ##-- state lookup from symbol string
 $q = $trie->a2q(\@ary);                ##-- ... or from array

 $str = $trie->q2s($q);                 ##-- string lookup from state
 \@syms = $trie->q2a($q);               ##-- ... or array lookup

 \@states = $trie->s2path($str);        ##-- state-path lookup from string
 \@states = $trie->a2path(\@syms);      ##-- ... or from array

 $out = $trie->q2out($q);               ##-- output lookup for state
 $out = $trie->s2out($str);             ##-- ... or for string
 $out = $trie->a2out(\@syms);           ##-- ... or for array

 ($q,$len) = $trie->s2prefixQ($str);    ##-- longest prefix lookup for string
 ($q,$len) = $trie->a2prefixQ(\@syms);  ##-- ... or for array

 $prefix = $trie->s2prefix($str);       ##-- longest matching prefix for string
 $prefix = $trie->a2prefix(\@syms);     ##-- ... or for array

 ##========================================================================
 ## Methods: Export: Gfsm

 $ilabs = $trie->gfsmInputLabels();         ##-- input alphabet
 $olabs = $trie->gfsmOutputLabels();        ##-- output alphabet
 $qlabs = $trie->gfsmStateLabels();         ##-- state alphabet

 $gfsmDFA = $trie->gfsmAutomaton(%args);    ##-- export as recognizer
 $gfsmFST = $trie->gfsmTransducer(%args);   ##-- export as transducer

 $outstr = out2str_default($out_or_undef);  ##-- default callback

 ##========================================================================
 ## Methods: Debug: View

 undef = $trie->viewps(%options);
 undef = $trie->drawDot($dotfile,%options);
 undef = $trie->viewfst(%options);
 undef = $trie->fstDot($dotfile,%options);

(Back to Top)

DESCRIPTION

Constructors etc.

new

 $obj = CLASS_OR_OBJ->new(%args);

Object structure / keyword %args:

  goto    => \@delta,   ##-- [$qid]{$sym} => $qid_to     s.t. $qid --$sym--> $qid_to
  rgoto   => \%rdelta,  ##-- [$qid_to]    => "$qid $sym" s.t. $qid --$sym--> $qid_to
  out     => \%output,  ##-- {$qid}       => $output_scalar
  chars   => \%chars,   ##-- {$char}      => undef
  cw      => $symbol_width, ##-- for string input
  nq      => $nstates,      ##-- scalar: number of states (E<gt>= 1)
  epsilon => $epsilon_str,  ##-- for gfsm label export

clone

 $trie2 = $trie->clone;

Create and return a new trie $trie2 as a copy of an existing trie $trie.

Methods: Construction

add

 $qid = $trie->add($str,$val);

Adds a path with one arc for each character in $str with path-output $val.

addArray

 $qid = $trie->addArray(\@syms,$val);

Adds a path with one arc for each element in \@syms with path-output $val.

remove

 undef = $trie->remove($str);

Hack: just removes output for $str

removeArray

 undef = $trie->removeArray(\@syms);

Hack: just removes output for \@syms.

Methods: Output packing

packout

 $trie = $trie->packout(%args);

Output packing utility, suitable for tries whose output function is a hash pseudo-set with numeric keys.

Recognized %args:

 packas => $pack_template_char,  ##-- either 'L' or 'S', default='L'
 packadd=> $int,                 ##-- value to add to ids when packing (default=0)

Methods: Lookup

s2q

 $q = $trie->s2q($str);

State lookup from input symbol string.

a2q

 $q = $trie->a2q(\@ary);

State lookup from input symbol array.

q2s

 $str = $trie->q2s($q);

Input string lookup from state.

q2a

 \@syms = $trie->q2a($q);

Input symbol array lookup from state.

s2path

 \@states = $trie->s2path($str);

State-path lookup from input symbol string.

a2path

 \@states = $trie->a2path(\@syms);

State-path lookup from input symbol array.

q2out

 $out = $trie->q2out($q);

Output value lookup from state.

s2out

 $out = $trie->s2out($str);

Output value lookup from input symbol string.

a2out

 $out = $trie->a2out(\@syms);

Output value lookup from input symbol array.

s2prefixQ

 ($q,$len) = $trie->s2prefixQ($str);
 $q        = $trie->s2prefixQ($str);

Longest prefix state lookup for input symbol string.

a2prefixQ

 ($q,$len) = $trie->a2prefixQ(\@syms);
 $q        = $trie->a2prefixQ(\@syms);

Longest prefix state lookup for input symbol array.

s2prefix

 $prefix = $trie->s2prefix($str);

Longest matching prefix lookup for input symbol string.

a2prefix

 $prefix = $trie->a2prefix(\@syms);

Longest matching prefix lookup for input symbol array.

Methods: Export: Gfsm

gfsmInputLabels

 $ilabs = $trie->gfsmInputLabels();
 $ilabs = $trie->gfsmInputLabels($labs)
 $ilabs = $trie->gfsmInputLabels($labs,%args)

Generate/alter input alphabet as a Gfsm::Alphabet object $labs.

Recognized %args:

 epsilon => $eps_str, ##-- default: $trie-E<gt>{epsilon}

gfsmOutputLabels

 $olabs = $trie->gfsmOutputLabels();
 $olabs = $trie->gfsmOutputLabels($labs,%args)

Generate/alter output alphabet as a Gfsm::Alphabet object $labs.

Recognized %args:

 out2str => \&sub,    ##-- strinfication callback for $out: default: perl stringification
 epsilon => $eps_str, ##-- default: $trie->{epsilon}

gfsmStateLabels

 $qlabs = $trie->gfsmStateLabels();

Generate/alter state alphabet as a Gfsm::Alphabet object $qlabs:

 $qlabs = $trie->gfsmStateLabels($qlabs)
 $qlabs = $trie->gfsmStateLabels($qlabs,%args)

Recognizd %args:

 out2str => \&sub ##-- called as $sub->($out_or_undef) : default: perl stringification

out2str_default

 $outstr = out2str_default($out_or_undef);

Default output stringification callback for e.g. gfsmStateLabels().

gfsmAutomaton

 $gfsmDFA = $trie->gfsmAutomaton(%args);

Export $trie as Gfsm::Automaton deterministic recognizer object.

Recognized %args:

 fsm     => $fsm,       ##-- output automaton
 ilabels => $inLabels,  ##-- default: $trie->gfsmInputLabels()
 dosort  => $bool,      ##-- sort automaton? (default=yes)

gfsmTransducer

 $gfsmFST = $trie->gfsmTransducer(%args);

Export $trie as Gfsm::Automaton transducer object.

Recognized %args:

 fsm     => $fsm,       ##-- output automaton
 ilabels => $inLabels,  ##-- default: $trie->gfsmInputLabels()
 olabels => $outLabels, ##-- default: $trie->gfsmOutputLabels()
 out2str => \&sub,      ##-- as for StateLabels(), OutputLabels()
 dosort  => $bool,      ##-- sort automaton? (default=yes)

Methods: Debug: View

viewps

 undef = $trie->viewps(%options);

(undocumented)

drawDot

 undef = $trie->drawDot($dotfile,%options);

(undocumented)

viewfst

 undef = $trie->viewfst(%options);

(undocumented)

fstDot

 undef = $trie->fstDot($dotfile,%options);

(undocumented)

(Back to Top)

AUTHOR

Bryan Jurish <moocow@ling.uni-potsdam.de>

(Back to Top)

COPYRIGHT AND LICENSE

Copyright (C) 2006 by Bryan Jurish

This package is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.8.4 or, at your option, any later version of Perl 5 you may have available.

(Back to Top)