Реализовать sortedMap с сопоставлением подпоследовательностей

Подводя итог тому, что я написал в комментариях, я бы сделал это следующим образом:

1. Создайте дополнительный индекс HashMap с записями [двухсимвольная подпоследовательность -> список слов].
2. При добавлении: генерировать все отдельные 2-символьные подпоследовательности из заданного слова, добавлять это слово к каждой соответствующей записи индексной карты.
3. При запросе: генерировать все отдельные 2-символьные подпоследовательности из запроса, среди них находить ту, которая соответствует кратчайшему списку в индексной карте, брать этот список. Отфильтруйте его по полному запросу и соберите соответствующие значения с основной карты.

Если запрос состоит из одного символа, то выполнить полную проверку. Я считаю, что это будет иметь лучшее пространство/сложность, чем создание дополнительного индекса для одиночных символов, особенно когда запросы с 1 символом встречаются редко.

Примечание. Мое решение работает в случае поиска подстроки. Читать редактировать.

Решение:

Используйте префиксную структуру данных: http://en.wikipedia.org/wiki/Trie

Вам нужно будет хранить:

abcd -> obj1

as:

abcd -> obj1
bcd -> obj1
cd -> obj1
d -> obj1

Чтобы найти свой результат, вы должны достаточно углубиться в попытку, чтобы удовлетворить условию, и оттуда найти все возможные решения.

Примеры:

ab -> obj1
cde -> obj1
bad -> obj2

Мы бы вставили следующие записи в наш Trie:

ab -> obj1
b -> obj1
cde -> obj1
de -> obj1
e -> obj1
bad -> obj2
ad -> obj2
d -> obj2

Теперь представьте, что мы ищем следующие записи:

d

Сначала переместитесь вниз для символа d в ​​Trie. После этого мы бы DFS. Мы уже находимся в obj2, и если мы перейдем к символу e в obj1. Таким образом, мы можем получить их обоих с записью d.

cd

Сначала мы переходим к персонажу c, а затем к персонажу d. Теперь мы используем DFS, и единственный путь, который мы можем найти, — это добавить символ e, который ведет к obj1.

efg

В Trie нет пути, удовлетворяющего нашему условию, поэтому мы не получаем решений.

ИЗМЕНИТЬ:

Мое решение работает, если мы ищем подстроку исходного элемента. Чтобы изменить мое решение, чтобы оно работало для любой незаразной подстроки, вам также придется вставить все перестановки в Trie.

Ваши «символы» могут быть интерпретированы как термины в традиционном И-запросе поисковой системы.

Из этого комментария:

все подпоследовательности abcd, такие как a,b,c,d,ab, ac, ad, bc, bd,cd , abc, abd, acd, abcd и т. д., при запросе должны возвращать подкарту с abcd -> obj1 как один из его входов.

Мы могли бы интерпретировать это с документом, содержащим термины Aspid Beaver Cherokee Deer (ABCD), документ должен быть возвращен при поиске любого из его слов или любой из их комбинаций.

Для этого вам нужно построить инвертированный индекс. Подробнее см. в этом ответе. По сути, вы должны построить HashMap или таблицу поиска (символов не так много) для каждого «символа» (=термин на языке поисковой системы), где поиск вернет все objX, где он появляется (=документ на языке поисковых систем), в идеале в порядке возрастания.

Чтобы найти все объекты, связанные с набором символов, вы должны объединить наборы для каждого отдельного символа. Поскольку они упорядочены, вы можете вычислить пересечение множества за линейное время.

Если запрос ba должен не совпадать с ключом abc, вы можете уточнить таблицу поиска / HashMap для хранения позиций символов (например: сохранить «b находится в Obj1 в позиции 0», «a найдено в Obj1 в позиции 1", вместо того, чтобы отбрасывать позиции). При вычислении поискового пересечения вы будете действовать в порядке поиска и отбрасывать совпадения с неправильным относительным порядком.

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

Изменить: Производительность

Если количество отдельных «терминов» невелико (например: 26 строчных английских букв), вы можете ускорить это, добавив n-граммы в качестве терминов (где для «abc» вы должны добавить «a», «b» , «с», «аб», «ас», «бк» и «абв»). Применяются те же правила - с половиной поисков и, поскольку ожидается перекрытие, можно использовать трюк Саши, чтобы избежать хранения индексов.

Вы можете попробовать aho-corasick с подстановочным знаком. Aho-Corasick — это более быстрый алгоритм сопоставления множественных шаблонов, и с подстановочным знаком он дает все подстроки. Вы можете попробовать мою реализацию php на codeplex (https://phpahocorasick.codeplex.com). Например, модульный тест с подстановочным знаком для шаблона гена:

$tree = new Ahocorasick\Ahocorasick();
$tree->add("AC");
$tree->add("GTG");
$tree->add("AACT");
echo $tree->match("ACCGAGTGCGTGGACAAACTACGATTGTGGAATGAACT","AC*GT");
$this->expectOutputString("ACCGAGT,ACCGAGTGCGT,ACCGAGTGCGTGGACAAACTACGATTGT,ACAAACTACGATTGT,ACTACGATTGT,ACGATTGT");