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

Question

Я хочу реализовать sortedMap с ключами и значениями, чтобы ключи можно было искать, предоставляя некоторую подпоследовательность. Например, карта содержит 3 записи:

abcd -> obj1 
def -> obj2 
abccd -> obj3 

Для запроса ac, результат должен быть подкарта, содержащей 1-й и 3-й запись, но для запроса acc, только третий вход должен быть возвращен.

Какую структуру данных следует использовать внутри, чтобы эффективно возвращать такой подкап? Например, Treemap, который хранит ключи в дереве (trie), чтобы эффективно возвращать подкачку на основе префикса?

Answer 1

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

Решение:

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

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

abcd -> obj1 

как:

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

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

Примеры:

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 нет пути, который удовлетворяет условию, поэтому мы не получаем решений.

EDIT:

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

Answer 2

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

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

все подпоследовательности ABCD, таких, как а, Ь, с, d, AB, AC, объявления, Ьс, шд, кд, ABC, ABD, ACD, ABCD и т. д., при запросе, должен возвращать подкачку с abcd -> obj1 в качестве одной из ее записей.

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

Что вы хотите построить для этого, это inverted index. См. this answer для более подробной информации. По существу, вы бы построили HashMap или таблицу поиска (не так много символов) для каждого символа (= термин в поисковике), где поиск вернет все objX, где он появится (= документ в поисковике-говорить), в идеале в порядке возрастания.

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

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

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

---

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

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

Answer 3

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

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

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

Answer 4

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

$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"); 

Answer 5

/** 
* @author viborole 
* 
*/ 
public class SortedMapSubsequence { 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    Map<String, String> data = new HashMap<String,String>(); 
    data.put("abcd", "obj1"); 
    data.put("def", "obj2"); 
    data.put("abccd", "obj3"); 
    String query="acc"; 
    search(query, data); 
} 

private static void search(String query, Map<String, String> data) { 
    for (Map.Entry<String, String> entry : data.entrySet()) 
    { 
     String key=entry.getKey(); 
     char[] k=key.toCharArray(); 
     char[] q=query.toCharArray(); 
     int kpos=0; 
     char[] found = new char[q.length]; 
     for(int i=0;i<q.length;i++){ 
      if(i>0){ 
       kpos++; 
      } 
      for(int j=kpos;j<k.length;j++){ 
       if(k[j]==q[i]){ 
        kpos=j; 
        found[i]=k[j]; 
        break; 
       } 
      } 
     } 
     if(Arrays.equals(found,q)){ 
      System.out.println("found : "+ entry.getValue()); 
     } 
    } 
} 

}