State-Aware Score-Decomposed Autocomplete

The problem

Standard autocomplete often struggles to provide accurate suggestions because it doesn't understand the specific context or multiple paths a user might be taking. It treats every word completion as an isolated choice rather than part of a larger flow.

What it does

It looks at multiple possible word completions at once and ranks them based on the specific context of the current state. It uses a specialized data structure to keep track of these different paths and their scores simultaneously.

Why it matters

It allows for more accurate and contextually relevant suggestions by evaluating multiple paths at once.

Validation

It was run in the sandbox and it failed. run output shows an error/traceback — the artifact does NOT run clean.

$ python3 state_aware_autocomplete_v2.py
Traceback (most recent call last):
  File "/work/state_aware_autocomplete.py", line 95, in <module>
    ac.add_word(word, score=len(word))
  File "/work/state_aware_autocomplete.py", line 53, in add_word
    self.dynsdt.add_score(word, score)
  File "/work/state_aware_autocomplete.py", line 15, in add_score
    nodes[i].scores[nodes[i-1].prefix] += score
                    ^^^^^^^^^^^^^^^^^
AttributeError: 'DynSDTNode' object has no attribute 'prefix'

No screenshot — there is nothing working to show. This is recorded as an unfinished sketch so the attempt stays visible instead of being quietly dropped.

The code

All of it — 121 lines, one file, standard library only.

from collections import defaultdict, deque
import sys

class DynSDTNode:
    def __init__(self):
        self.children = defaultdict(DynSDTNode)
        self.scores = defaultdict(int)
        self.is_end = False
        self.prefix_count = 0
        self.path_probability = 1.0  # New field for path probability

    def add_score(self, key, score):
        nodes = [self]
        for char in key:
            nodes.append(nodes[-1].children[char])
        for i in range(1, len(nodes)):
            nodes[i].scores[nodes[i-1].prefix] += score

    def update_prefix_counts(self):
        # Recursive count of all prefixes
        def dfs(node, prefix):
            if node.is_end:
                node.prefix_count += 1
            for char, child in node.children.items():
                dfs(child, prefix + char)
        dfs(self, '')

    def update_path_probability(self, path_prob):
        # Multiplier for path probability score
        self.path_probability = path_prob


class FlowCipherStateTracker:
    def __init__(self):
        self.current_state = deque(maxlen=5)  # Keep last 5 characters
        self.state_transitions = defaultdict(lambda: defaultdict(int))

    def update_state(self, char):
        self.current_state.append(char)
        if len(self.current_state) > 1:
            prev = self.current_state[-2]
            curr = char
            self.state_transitions[prev][curr] += 1

    def get_weight(self, char):
        if not self.current_state:
            return 1.0
        last_char = self.current_state[-1]
        total = sum(self.state_transitions[last_char].values())
        return self.state_transitions[last_char].get(char, 0) / (total or 1)

    def get_path_probability(self):
        # Calculate joint probability of current state path
        if len(self.current_state) < 2:
            return 1.0
        prob = 1.0
        for i in range(1, len(self.current_state)):
            prev = self.current_state[i-1]
            curr = self.current_state[i]
            total = sum(self.state_transitions[prev].values())
            if total == 0:
                return 0.0  # Impossible transition
            prob *= self.state_transitions[prev][curr] / total
        return prob


class StateAwareAutocomplete:
    def __init__(self):
        self.dynsdt = DynSDTNode()
        self.state_tracker = FlowCipherStateTracker()

    def add_word(self, word, score=1):
        # Add to DynSDT with score decomposition
        self.dynsdt.add_score(word, score)
        # Update state transitions
        for i in range(1, len(word)):
            prev_char = word[i-1]
            curr_char = word[i]
            self.state_tracker.state_transitions[prev_char][curr_char] += 1

    def update_context(self, char):
        self.state_tracker.update_state(char)
        return self._autocomplete(char)

    def _autocomplete(self, prefix_char=None):
        # Get current state context
        context_weight = self.state_tracker.get_weight(prefix_char or ' ')
        # Calculate path probabilities for current context
        path_prob = self.state_tracker.get_path_probability()
        # Find nodes matching current state
        nodes = [self.dynsdt]
        for char in self.state_tracker.current_state:
            if char in nodes[-1].children:
                nodes.append(nodes[-1].children[char])
            else:
                nodes = [self.dynsdt]  # Reset on mismatch
        # Score and rank completions
        results = []
        def search(node, prefix):
            if node.is_end:
                # Combine original scoring with path probability multiplier
                node.path_probability *= path_prob
                results.append((prefix, node.prefix_count * context_weight * node.path_probability))
            for char, child in node.children.items():
                search(child, prefix + char)
        search(nodes[-1], ''.join(self.state_tracker.current_state))
        # Sort by combined score
        results.sort(key=lambda x: x[1], reverse=True)
        return [item[0] for item in results[:10]]  # Top 10 results

# Example usage
if __name__ == '__main__':
    ac = StateAwareAutocomplete()
    words = ['apple', 'apparel', 'apricot', 'application', 'appetite']
    for word in words:
        ac.add_word(word, score=len(word))  # Score by word length
    # Simulate typing context
    context = 'app'
    for char in context:
        ac.update_context(char)
    print('Autocomplete suggestions:', ac._autocomplete())