Буду рад любой информации относительно алгоритмов поиска по тегам.

Немного объясню что имеется в виду на примере:

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

Так же необходимо предусмотреть замену тегов, то есть скажем тег яркая = (яркий, контрастный,контрастная, земетный ...)

Вот интересно какбы это реализовать структуру хранения данных, чтобы поиск был максимально быстрым и полным.

Структура данных подбиратся, исходя из требований по соотношению производительности различных операций.
Насколько я понял из условия, поиск - процедура намного более частая, чем вставка нового объекта. В этих условиях хорошим вариантом будет упорядоченный по алфавиту массив (поиск O(log(n)), вставка O(n)).
Каждый объект - ключевое слово(строка) + список синоимов(указатель).