Fixed removal in per-doc-priority-queue
diff --git a/lib/Krawfish/Index/Store/Dynamic/Dictionary.pm b/lib/Krawfish/Index/Store/Dynamic/Dictionary.pm
index f0f9d9b..4b7ac01 100644
--- a/lib/Krawfish/Index/Store/Dynamic/Dictionary.pm
+++ b/lib/Krawfish/Index/Store/Dynamic/Dictionary.pm
@@ -5,6 +5,20 @@
# TODO:
# Add parent transitions and support
# term(leaf-node)
+#
+# TODO:
+# The self-optimizing application should also
+# be used for autosuggestions.
+# This will be a separate datastructure
+# that optimizes on update (when a user searches for a term).
+# The dictionary should have a node-count and a node-limit.
+# When the node limit is exceeded on update, the datastructure
+# will remove the randomized least significant dictionary entries,
+# until the node-limit is again fine.
+# That will require the APIs:
+# ->prefix_lookup($prefix, $top_k);
+# ->update($term, $so-action)
+# ->remove_least_significant_term();
use constant {
SPLIT_CHAR => 0,
@@ -113,4 +127,36 @@
sub search_i;
+sub prefix_lookup {
+ my ($self, $prefix, $top_k) = @_;
+ ...
+};
+
+sub update {
+ my ($self, $prefix, $so_strategy) = @_;
+ ...
+};
+
+# Remove least significant term
+sub remove_lst {
+ my $self = shift;
+ # On every level:
+ my $node;
+ if (!$node->[LO_KID] && !$node->[HI_KID]) {
+ $node = $node->[EQ_KID];
+ }
+ elsif ($node->[LO_KID] && $node->[HI_KID]) {
+ $node = int(rand(2)) ? $node->[LO_KID] : $node->[HI_KID];
+ }
+ elsif ($node->[LO_KID]) {
+ $node = $node->[LO_KID];
+ }
+ else {
+ $node = $node->[HI_KID];
+ };
+
+ # Delete node
+ ...
+};
+
1;
diff --git a/lib/Krawfish/Index/Store/V1/Dictionary.pm b/lib/Krawfish/Index/Store/V1/Dictionary.pm
index 776c1a6..bea59a1 100644
--- a/lib/Krawfish/Index/Store/V1/Dictionary.pm
+++ b/lib/Krawfish/Index/Store/V1/Dictionary.pm
@@ -5,16 +5,26 @@
use Memoize;
use POSIX qw/floor/;
+# This is necessary to deal with the dynamic structure
use constant {
SPLIT_CHAR => 0,
- LO_KID => 1,
- EQ_KID => 2,
- HI_KID => 3,
- TERM_ID => 4,
- TERM_CHAR => '00',
- DEBUG => 0
+ LO_KID => 1,
+ EQ_KID => 2,
+ HI_KID => 3,
+ TERM_ID => 4,
+ TERM_CHAR => '00',
+ DEBUG => 0
};
+# TODO:
+# - The datastructure should be rather like:
+# (([LENGTH-first-bit-not-set][xor][char])|([xor-first-bit-set][char]))*
+# Because then there is no need for length-1 information.
+# It may also be beneficial to have the information of a leaf node
+# directly encoded in the xor, though this may be complicated,
+# leaving only 30bit for xor
+# - Characters are stored as UTF-32
+
# This is a very compact representation of a Ternary Search Tree.
# On each letter node, the binary search tree is complete and stored
# in an array. The parental relation is implemented using a