Двоетапна стратегія пошуку у векторних кодових книгах для ущільнення мовлення

Abstract

Розроблено підхід, який дозволяє поєднати переваги методів швидкого пошуку найближчого сусіда у кодових книгах із застосуванням зваженої евклідової метрики. Запропонована двоетапна стратегія пошуку полягає в тому, що на першому етапі з кодової книги, структурованої на основі бінарного дерева, за евклідовою метрикою відбирається невелика кількість векторів (кандидатів), з яких на другому етапі із використанням ваг обирається вектор, найближчий до вхідного. Отримано аналітичні залежності кількості кандидатів та операцій, необхідних для пошуку найближчого вектора. Наведено результати експериментів, що підтверджують ефективність запропонованого підходу.

Разработан подход, сочетающий преимущества методов быстрого поиска ближайшего соседа в кодовых книгах с применением взвешенной евклидовой метрики. Предлагаемая двухэтапная стратегия поиска заключается в том, что на первом этапе из кодовой книги, структурированной на основе бинарного дерева, по евклидовой метрике отбирается небольшое количество векторов (кандидатов), из числа которых на втором этапе с использованием весов выбирается вектор, ближайший к входному. Получены аналитические зависимости числа кандидатов и количества операций, необходимых для поиска ближайшего вектора. Приведены результаты экспериментов, подтверждающие эффективность предлагаемого подхода.

There has been developed the approach, which combines the advantages of the fast nearest neighbor search in the codebooks using weighted Euclidean metric. The proposed two-step search strategy is that: at first on the basis of the binary tree a few of codebook vectors (candidates) are chosen, using Euclidean metrics; among which then really the nearest vector is chosen. It is deduced the analytical dependence of the candidates and the number of operations needed to find the nearest vector. The given results of experiments confirm the performance of the proposed approach.