Improve TST structure
diff --git a/lib/Krawfish/Index/Dictionary.pm b/lib/Krawfish/Index/Dictionary.pm
index 8eeb00d..0f682ff 100644
--- a/lib/Krawfish/Index/Dictionary.pm
+++ b/lib/Krawfish/Index/Dictionary.pm
@@ -243,7 +243,7 @@
my $self = shift;
# TODO:
# For prefix rank:
- # Iterate over prefix tree in alphabetical order
+ # Iterate over prefix tree in in-node order
# and generate a rank for the subtree of the subterm.
# ...
# For suffix rank:
diff --git a/lib/Krawfish/Index/Store/Dynamic/Dictionary.pm b/lib/Krawfish/Index/Store/Dynamic/Dictionary.pm
index 4deb110..0dcaa2b 100644
--- a/lib/Krawfish/Index/Store/Dynamic/Dictionary.pm
+++ b/lib/Krawfish/Index/Store/Dynamic/Dictionary.pm
@@ -19,20 +19,21 @@
sub insert {
# Iterative implementation of string insertion.
- my ($self, $str, $term_id) = @_;
+ my ($self, $term, $term_id) = @_;
# The string ends with a terminal transition
- my (@char) = (split(//, $str), TERM_CHAR);
+ my (@char) = (split(//, $term), TERM_CHAR);
my $ref = $self;
my $retval = undef;
+ my $i = 0;
- while (@char) {
+ # Fetch first character
+ while (my $char = $char[$i]) {
- my $char = $char[0];
-
- if (! defined $ref->[SPLIT_CHAR]) { # We use defined() to avoid
- # auto-vivification.
+ # We use defined() to avoid
+ # auto-vivification.
+ if (! defined $ref->[SPLIT_CHAR]) {
# create a new node
$ref->[LO_KID] = [];
@@ -54,10 +55,11 @@
}
else {
$ref = $ref->[EQ_KID];
- shift @char;
+ $i++;
};
};
};
+
$retval;
};
diff --git a/lib/Krawfish/Index/Store/V1/Dictionary.pm b/lib/Krawfish/Index/Store/V1/Dictionary.pm
index 0c2528d..addf731 100644
--- a/lib/Krawfish/Index/Store/V1/Dictionary.pm
+++ b/lib/Krawfish/Index/Store/V1/Dictionary.pm
@@ -59,12 +59,13 @@
my $length = $self->[$pos] * 2; # Length (e.g. 4 bytes char + 4 bytes xor)
my $node_i = 1;
my $node_char;
+ my $i = 0;
# Character at node position
while ($node_char = $self->[$pos + $node_i]) {
# Check for right child
- my $char = $char[0];
+ my $char = $char[$i] or return;
print_log('v1_dict', "$char vs $node_char") if DEBUG;
@@ -108,9 +109,12 @@
# Move eq-node
print_log('v1_dict', "Next node is at offset $pos") if DEBUG;
+ # Get the length of the BST
$length = $self->[$pos] * 2;
+
+ # Get the root node offset
$node_i = 1;
- shift @char;
+ $i++;
};
};
undef;
@@ -137,52 +141,6 @@
-
-
-
-
-# Nils Diewald:
-# That's my trial to create a maximum compact dictionary
-sub XXX_breadth_first {
- my $dynamic_node = shift;
-
- # Do a breadth-first search per node
- my @queue = ($dynamic_node);
- my @results = ();
-
- while (scalar(@queue) != 0) {
-
- # Get the first item
- $dynamic_node = shift @queue;
-
- push @queue, $dynamic_node->[LO_KID] if $dynamic_node->[LO_KID]->[0];
- push @queue, $dynamic_node->[HI_KID] if $dynamic_node->[HI_KID]->[0];
- push @results, $dynamic_node->[SPLIT_CHAR];
- };
-
- return \@results;
-};
-
-
-sub XXX_depth_first {
- my $dynamic_node = shift;
-
- my @stack = ($dynamic_node);
- my @results = ();
-
- while (scalar(@stack) != 0) {
- $dynamic_node = pop @stack;
-
- push @stack, $dynamic_node->[LO_KID] if $dynamic_node->[LO_KID]->[0];
- push @stack, $dynamic_node->[HI_KID] if $dynamic_node->[HI_KID]->[0];
-
- push @results, $dynamic_node->[SPLIT_CHAR];
- };
-
- return \@results;
-};
-
-
# Traverse the current level tree in-order to
# get nodes in alphabetic order
sub _in_order {
@@ -376,3 +334,55 @@
1;
+
+
+__END__
+
+
+
+
+
+
+
+
+# Nils Diewald:
+# That's my trial to create a maximum compact dictionary
+sub XXX_breadth_first {
+ my $dynamic_node = shift;
+
+ # Do a breadth-first search per node
+ my @queue = ($dynamic_node);
+ my @results = ();
+
+ while (scalar(@queue) != 0) {
+
+ # Get the first item
+ $dynamic_node = shift @queue;
+
+ push @queue, $dynamic_node->[LO_KID] if $dynamic_node->[LO_KID]->[0];
+ push @queue, $dynamic_node->[HI_KID] if $dynamic_node->[HI_KID]->[0];
+ push @results, $dynamic_node->[SPLIT_CHAR];
+ };
+
+ return \@results;
+};
+
+
+sub XXX_depth_first {
+ my $dynamic_node = shift;
+
+ my @stack = ($dynamic_node);
+ my @results = ();
+
+ while (scalar(@stack) != 0) {
+ $dynamic_node = pop @stack;
+
+ push @stack, $dynamic_node->[LO_KID] if $dynamic_node->[LO_KID]->[0];
+ push @stack, $dynamic_node->[HI_KID] if $dynamic_node->[HI_KID]->[0];
+
+ push @results, $dynamic_node->[SPLIT_CHAR];
+ };
+
+ return \@results;
+};
+