array_trie_compact/test.py at main · Jimmymonster/array_trie_compact · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
from Trie_dict import CompressedArrayTrie

# Comprehensive test suite
def test_zero_fragmentation():
    print("Testing Zero-Fragmentation CompressedArrayTrie\n")

    test_cases = [
        {
            'name': 'Simple words',
            'keywords': ['cat', 'car', 'card', 'care', 'careful'],
            'text': 'The cat in the car was very careful with cards'
        },
        {
            'name': 'Prefix chains',
            'keywords': ['a', 'ab', 'abc', 'abcd', 'abcde'],
            'text': 'abcdef contains multiple prefixes'
        },
        {
            'name': 'Common prefixes',
            'keywords': ['hello', 'help', 'hero', 'her', 'he'],
            'text': 'hello hero, can you help her?'
        },
        {
            'name': 'Single character',
            'keywords': ['a', 'i'],
            'text': 'a quick brown fox jumps, i think'
        },
        {
            'name': 'Empty case',
            'keywords': [],
            'text': 'no keywords to find'
        },
        {
            'name': 'Large case',
            'keywords': [f'word{i}' for i in range(100)] + ['test', 'testing', 'tester'],
            'text': 'word42 and word99 are testing the tester'
        },
        {
            'name': 'No matches',
            'keywords': ['xyz', 'abc'],
            'text': 'no matching words here'
        }
    ]

    for case in test_cases:
        print(f"\n{'='*20} {case['name']} {'='*20}")

        trie = CompressedArrayTrie()
        trie.build(case['keywords'])

        # Print statistics
        trie.print_detailed_stats()

        # Verify integrity
        trie.verify_integrity(case['keywords'])

        if case['keywords']:  # Skip search for empty case
            # Test search
            positions = trie.search_positions(case['text'])
            matches = trie.search_all_matches(case['text'])

            print(f"\nSearch Results:")
            print(f"Text: '{case['text']}'")
            print(f"Match positions: {positions}")
            print(f"All matches: {[(start, end, word) for start, end, word in matches]}")

        print()

if __name__ == "__main__":
    test_zero_fragmentation()