сложность построения списка инвертированных индексов

Даны n строки S1, S2, ..., Sn и набор алфавитов A={a_1,a_2,....,a_m}. Предположим, что все алфавиты в каждой строке различны. Теперь я хочу создать инвертированный индекс для каждого a_i (i=1,2...,m). В моем инвертированном индексе тоже есть кое-что особенное: алфавиты в A расположены в некотором последовательном порядке, если в инвертированный индекс a_i включена одна строка (скажем, S_2), то a_j (j=i+1,i+2,...,m) больше не нужно включать S_2. Короче говоря, каждая строка появляется в инвертированном списке только один раз. Мой вопрос в том, как создать такой список быстро и эффективно? В любое время сложность ограничена?

Например, A={a,b,e,g}, S1={abg}, S2={bg}, S3={gae}, S4={g}. Тогда мой инвертированный список должен быть:

a: S1,S3
b: S2     (since S1 has appeared previously, so we don't need to include it here)
e: 
g: S4

string optimization performance algorithm inverted-index
person John Smith    schedule 06.09.2012    source источник
comment
Просто интересно: есть ли причина, по которой S4 не будет под индексом «а»? Индекс должен быть каким-то образом сбалансирован? Если нет, то кажется, что достаточно посмотреть на первый символ каждой строки и поместить его под этот индекс. Хотя, возможно, я не понимаю проблемы.   -  person Nathan Andrew Mullenax    schedule 06.09.2012
comment
Это моя проблема. Теперь исправлено, спасибо!   -  person John Smith    schedule 06.09.2012
comment
Не во всех случаях, если S3={gae}   -  person John Smith    schedule 06.09.2012
comment
Думаю, теперь я понимаю — в таком случае, кажется, у Данте есть ответ. Единственная оптимизация, которую я могу придумать, - это остановить просмотр определенной строки, если вы встретите наименьший символ алфавита.   -  person Nathan Andrew Mullenax    schedule 06.09.2012
comment
Дело в том, что количество строк намного больше, чем количество алфавитов. Так есть ли способ улучшить его?   -  person John Smith    schedule 06.09.2012

Ответы (1)


arrow_upward
3
arrow_downward

Если я правильно понял ваш вопрос, простое решение:

for each string in n strings
    find the "smallest" character in the string
    put the string in the list for the character

Сложность пропорциональна общей длине строк, умноженной на константу для проверки порядка.

Если есть простой способ проверки (например, символы в алфавитном порядке и все в нижнем регистре, ‹ будет достаточно), просто сравните их; в противном случае предлагаю использовать хеш-таблицу, каждая пара которой — символ и его порядок, позже просто сравнить их.

person Dante May Code    schedule 06.09.2012