Trie, Radix и Patricia

<?php

declare(strict_types=1);

/**
 * Standard trie for string autocomplete.
 * For production at scale use FST (Finite State Transducer) or marisa-trie.
 */
final class TrieNode
{
    /** @var array<string, TrieNode> */
    public array $children = [];
    public bool $isEnd = false;
    public int $rank = 0; // popularity / frequency for ranking
}

final class Trie
{
    private TrieNode $root;

    public function __construct()
    {
        $this->root = new TrieNode();
    }

    public function insert(string $word, int $rank = 1): void
    {
        $node = $this->root;
        foreach (mb_str_split(mb_strtolower($word)) as $ch) {
            if (!isset($node->children[$ch])) {
                $node->children[$ch] = new TrieNode();
            }
            $node = $node->children[$ch];
        }
        $node->isEnd = true;
        $node->rank = max($node->rank, $rank);
    }

    public function contains(string $word): bool
    {
        $node = $this->descend($word);
        return $node !== null && $node->isEnd;
    }

    /**
     * Return up to $limit suggestions for given prefix, sorted by rank desc.
     * @return list<array{word: string, rank: int}>
     */
    public function autocomplete(string $prefix, int $limit = 10): array
    {
        $node = $this->descend($prefix);
        if ($node === null) {
            return [];
        }

        $results = [];
        $this->collect($node, mb_strtolower($prefix), $results);

        usort($results, fn(array $a, array $b): int => $b['rank'] <=> $a['rank']);

        return array_slice($results, 0, $limit);
    }

    private function descend(string $prefix): ?TrieNode
    {
        $node = $this->root;
        foreach (mb_str_split(mb_strtolower($prefix)) as $ch) {
            if (!isset($node->children[$ch])) {
                return null;
            }
            $node = $node->children[$ch];
        }
        return $node;
    }

    /** @param list<array{word: string, rank: int}> $results */
    private function collect(TrieNode $node, string $path, array &$results): void
    {
        if ($node->isEnd) {
            $results[] = ['word' => $path, 'rank' => $node->rank];
        }
        foreach ($node->children as $ch => $child) {
            $this->collect($child, $path . $ch, $results);
        }
    }
}

// Usage
// $trie = new Trie();
// $trie->insert('golang', rank: 1000);
// $trie->insert('google', rank: 5000);
// $trie->insert('go', rank: 500);
// print_r($trie->autocomplete('go', limit: 3));
// // [['word'=>'google', 'rank'=>5000], ['word'=>'golang', 'rank'=>1000], ['word'=>'go', 'rank'=>500]]

package trie

import (
	"sort"
	"strings"
)

type node struct {
	children map[rune]*node
	isEnd    bool
	rank     int
}

func newNode() *node { return &node{children: map[rune]*node{}} }

// Trie is a simple prefix tree for autocomplete.
type Trie struct{ root *node }

// New returns an empty trie.
func New() *Trie { return &Trie{root: newNode()} }

// Insert adds word with given rank (higher = more popular).
func (t *Trie) Insert(word string, rank int) {
	n := t.root
	for _, r := range strings.ToLower(word) {
		child, ok := n.children[r]
		if !ok {
			child = newNode()
			n.children[r] = child
		}
		n = child
	}
	n.isEnd = true
	if rank > n.rank {
		n.rank = rank
	}
}

// Suggestion is an autocomplete result.
type Suggestion struct {
	Word string
	Rank int
}

// Autocomplete returns up to limit suggestions matching prefix, sorted by rank desc.
func (t *Trie) Autocomplete(prefix string, limit int) []Suggestion {
	n := t.root
	prefix = strings.ToLower(prefix)
	for _, r := range prefix {
		child, ok := n.children[r]
		if !ok {
			return nil
		}
		n = child
	}

	var results []Suggestion
	var collect func(*node, string)
	collect = func(n *node, path string) {
		if n.isEnd {
			results = append(results, Suggestion{Word: path, Rank: n.rank})
		}
		for r, c := range n.children {
			collect(c, path+string(r))
		}
	}
	collect(n, prefix)

	sort.Slice(results, func(i, j int) bool { return results[i].Rank > results[j].Rank })
	if limit > 0 && len(results) > limit {
		results = results[:limit]
	}
	return results
}

using System;
using System.Collections.Generic;
using System.Linq;

public readonly record struct Suggestion(string Word, int Rank);

// Standard trie for string autocomplete.
// For production at scale use an FST (Finite State Transducer) instead.
internal sealed class TrieNode
{
    public Dictionary<char, TrieNode> Children { get; } = [];
    public bool IsEnd { get; set; }
    public int Rank { get; set; } // popularity / frequency for ranking
}

public sealed class Trie
{
    private readonly TrieNode _root = new();

    // Insert adds a word with the given rank (higher = more popular).
    public void Insert(string word, int rank = 1)
    {
        var node = _root;
        foreach (var ch in word.ToLowerInvariant())
        {
            if (!node.Children.TryGetValue(ch, out var child))
            {
                child = new TrieNode();
                node.Children[ch] = child;
            }
            node = child;
        }

        node.IsEnd = true;
        node.Rank = Math.Max(node.Rank, rank);
    }

    public bool Contains(string word) => Descend(word) is { IsEnd: true };

    // Return up to `limit` suggestions for the prefix, sorted by rank descending.
    public List<Suggestion> Autocomplete(string prefix, int limit = 10)
    {
        var normalized = prefix.ToLowerInvariant();
        var node = Descend(normalized);
        if (node is null)
        {
            return [];
        }

        var results = new List<Suggestion>();
        Collect(node, normalized, results);

        return results
            .OrderByDescending(s => s.Rank)
            .Take(limit)
            .ToList();
    }

    private TrieNode? Descend(string prefix)
    {
        var node = _root;
        foreach (var ch in prefix.ToLowerInvariant())
        {
            if (!node.Children.TryGetValue(ch, out var child))
            {
                return null;
            }
            node = child;
        }
        return node;
    }

    private static void Collect(TrieNode node, string path, List<Suggestion> results)
    {
        if (node.IsEnd)
        {
            results.Add(new Suggestion(path, node.Rank));
        }

        foreach (var (ch, child) in node.Children)
        {
            Collect(child, path + ch, results);
        }
    }
}

// Usage:
// var trie = new Trie();
// trie.Insert("golang", rank: 1000);
// trie.Insert("google", rank: 5000);
// trie.Insert("go", rank: 500);
// trie.Autocomplete("go", limit: 3); // google, golang, go

from __future__ import annotations

from dataclasses import dataclass, field

@dataclass(slots=True)
class TrieNode:
    """Standard trie node.

    For production at scale use an FST or marisa-trie instead.
    """

    children: dict[str, "TrieNode"] = field(default_factory=dict)
    is_end: bool = False
    rank: int = 0  # popularity / frequency for ranking

class Trie:
    def __init__(self) -> None:
        self._root = TrieNode()

    def insert(self, word: str, rank: int = 1) -> None:
        """Add a word with the given rank (higher = more popular)."""
        node = self._root
        for ch in word.lower():
            node = node.children.setdefault(ch, TrieNode())

        node.is_end = True
        node.rank = max(node.rank, rank)

    def __contains__(self, word: str) -> bool:
        node = self._descend(word)
        return node is not None and node.is_end

    def autocomplete(self, prefix: str, limit: int = 10) -> list[tuple[str, int]]:
        """Return up to `limit` (word, rank) pairs, sorted by rank descending."""
        normalized = prefix.lower()
        node = self._descend(normalized)
        if node is None:
            return []

        results = list(self._collect(node, normalized))
        results.sort(key=lambda pair: pair[1], reverse=True)
        return results[:limit]

    def _descend(self, prefix: str) -> TrieNode | None:
        node = self._root
        for ch in prefix.lower():
            child = node.children.get(ch)
            if child is None:
                return None
            node = child
        return node

    def _collect(self, node: TrieNode, path: str):
        if node.is_end:
            yield path, node.rank
        for ch, child in node.children.items():
            yield from self._collect(child, path + ch)

# Usage:
# trie = Trie()
# trie.insert("golang", rank=1000)
# trie.insert("google", rank=5000)
# trie.insert("go", rank=500)
# trie.autocomplete("go", limit=3)
# # [("google", 5000), ("golang", 1000), ("go", 500)]