State Set Index Laravel Package

Getting Started

Minimal Setup

1. Install the package:

   composer require toflar/state-set-index
   

2. Basic index creation (e.g., in a service class or Laravel service provider):

   use Toflar\StateSetIndex\StateSetIndex;
   use Toflar\StateSetIndex\Config;
   use Toflar\StateSetIndex\Alphabet\Utf8Alphabet;
   use Toflar\StateSetIndex\DataStore\InMemoryDataStore;
   use Toflar\StateSetIndex\StateSet\InMemoryStateSet;
   
   $index = new StateSetIndex(
       new Config(6, 4), // (maxIndexLength, alphabetSize)
       new Utf8Alphabet(),
       new InMemoryStateSet(),
       new InMemoryDataStore()
   );
   

3. Index your data (e.g., in a boot() method or command):

   $index->index(['Mueller', 'Müller', 'Muentner', 'Muster', 'Mustermann']);
   

4. First search (e.g., in a controller or API endpoint):

   $results = $index->find('Mustre', 2); // Returns ['Muster']
   

Where to Look First

• Config: Adjust maxIndexLength and alphabetSize based on your dataset size and expected query patterns (see paper for guidance).
• Alphabet: Use Utf8Alphabet for most cases; customize only if you need non-UTF-8 mappings.
• Storage: Start with InMemoryStateSet and InMemoryDataStore for prototyping; replace with persistent implementations (e.g., Redis, database) for production.

Implementation Patterns

Core Workflow: Indexing and Searching

1. Indexing:

   // One-time setup (e.g., during app boot)
   $index->index($yourDataArray);
   
   // Dynamic updates (e.g., in a queue job)
   $index->add(['new_entry1', 'new_entry2']);
   $index->remove(['old_entry']); // Requires v3.0.0+
   

2. Searching:

   // Basic search (returns filtered results)
   $matches = $index->find('query', 2); // Max Levenshtein distance = 2
   
   // Intermediate results (for custom post-processing)
   $states = $index->findMatchingStates('query', 2);
   $strings = $index->findAcceptedStrings('query', 2); // Unfiltered (may include false positives)
   

3. Incremental Search (e.g., autocomplete):

   // Initial snapshot (e.g., on user input 'Muel')
   $snapshot = $index->createMatchingStatesSnapshot('Muel', 1, 1);
   
   // Continue with next character (e.g., 'Mueler')
   $continued = $index->continueMatchingStatesSnapshot('Mueler', $snapshot);
   $states = $continued->matchingStates();
   

Laravel-Specific Patterns

1. Service Container Binding:

   // In a service provider
   $this->app->singleton(StateSetIndex::class, function ($app) {
       return new StateSetIndex(
           new Config(6, 4),
           new Utf8Alphabet(),
           new InMemoryStateSet(), // Replace with RedisStateSet in production
           new InMemoryDataStore()
       );
   });
   

2. Command-Line Indexing (e.g., php artisan index:update):

   use Illuminate\Console\Command;
   use Toflar\StateSetIndex\StateSetIndex;
   
   class IndexUpdateCommand extends Command {
       protected $signature = 'index:update';
       protected $description = 'Update the state set index';
   
       public function handle(StateSetIndex $index) {
           $newData = $this->getNewDataFromDatabase();
           $index->index($newData);
           $this->info('Index updated!');
       }
   }
   

3. Caching Snapshots (e.g., for autocomplete):

   // In a controller or middleware
   $cacheKey = 'autocomplete:snapshot:' . $userId . ':' . $queryPrefix;
   $snapshot = cache($cacheKey);
   
   if (!$snapshot) {
       $snapshot = $index->createMatchingStatesSnapshot($queryPrefix, 2, 1);
       cache()->put($cacheKey, $snapshot, now()->addMinutes(5));
   }
   
   $results = $index->continueMatchingStatesSnapshot($fullQuery, $snapshot);
   

Performance Optimization Patterns

1. Config Tuning:

   • Start with maxIndexLength = 6 and alphabetSize = 4 for most use cases.
   • Increase maxIndexLength for longer strings (e.g., 8–12 for sentences).
   • Adjust alphabetSize based on character diversity (higher for multilingual data).

2. Persistent Storage:

   • Replace InMemoryStateSet with a database-backed implementation (e.g., using Laravel’s Eloquent or a Redis adapter).
   • Example Redis adapter (pseudo-code):

     class RedisStateSet implements StateSetInterface {
         public function has(int $state): bool {
             return Redis::hexists('stateset', $state);
         }
         // Implement other methods...
     }
     

3. Batch Processing:

   • Index data in batches to avoid memory issues:

     $batchSize = 1000;
     foreach (array_chunk($largeDataset, $batchSize) as $batch) {
         $index->index($batch);
     }
     

Gotchas and Tips

Common Pitfalls

1. False Positives:

   • findAcceptedStrings() may return false positives (strings not matching the query but passing the Levenshtein filter). Always use find() for production results.
   • Fix: Post-process results if needed:

     $candidates = $index->findAcceptedStrings('query', 2);
     $matches = array_filter($candidates, function ($str) use ($query) {
         return levenshtein($query, $str) <= 2;
     });
     

2. Snapshot Invalidation:

   • Snapshots become stale if the index changes. Always invalidate caches after index(), add(), or remove():

     $index->remove(['old_entry']);
     Cache::forget('autocomplete:snapshot:*'); // Invalidate all snapshots
     

3. Memory Usage:

   • InMemoryStateSet and InMemoryDataStore load the entire index into memory. For large datasets (>100K entries), use persistent storage.
   • Tip: Monitor memory usage with memory_get_usage() during indexing.

4. Transposition Quirks:

   • The package supports transpositions (e.g., "ab" ↔ "ba") via Damerau-Levenshtein (v3.0.0+), but this increases index size and search time.
   • Tip: Disable if not needed by using a custom AlphabetInterface that ignores transpositions.

5. UTF-8 Handling:

   • Utf8Alphabet uses UTF-8 codepoints, which may not align with your expectations for certain characters (e.g., accented letters).
   • Tip: Extend Utf8Alphabet for custom mappings:

     class CustomAlphabet implements AlphabetInterface {
         public function map(string $char, int $alphabetSize): int {
             $normalized = Normalizer::normalize($char, Normalizer::FORM_D);
             return crc32($normalized) % $alphabetSize;
         }
     }
     

Debugging Tips

1. Verify Index Integrity:

   • Check if a string was indexed correctly:

     $states = $index->findMatchingStates('exact_match', 0);
     $strings = $index->findAcceptedStrings('exact_match', 0);
     

2. Log Intermediate States:

   • Debug snapshots by logging matching states:

     $snapshot = $index->createMatchingStatesSnapshot('pre', 1, 1);
     $states = $snapshot->matchingStates();
     Log::debug('Snapshot states:', ['states' => $states]);
     

3. Performance Profiling:

   • Use Laravel’s debugbar or Xdebug to profile find() calls:

     $timer = new \Symfony\Component\Stopwatch\Stopwatch();
     $timer->start('state_set_index');
     $results = $index->find('query', 2);
     $event = $timer->stop('state_set_index');
     Log::info('Index search time:', ['ms' => $event->getDuration()]);
     

Extension Points

1. Custom Alphabet:
   • Implement AlphabetInterface for domain-specific character mappings (e.g., phonetic alphabets):

     class PhoneticAlphabet implements Alphabet