Здравствуйте, SergASh, Вы писали:

SAS>Например, словарь такой:
SAS>

SAS>[ 5, 15] -> Царь
SAS>[35, 50] -> Медведь
SAS>[25, 40] -> Чурка
SAS>

SAS>Подаем на вход [10, 30], получаем
SAS>

SAS>[ 5, 15] -> Царь
SAS>[25, 40] -> Чурка
SAS>

у нас в Nitra

Автор: VladD2
Дата: 18.12.15

похожим образом хранятся позиции в тексте. Для каждого элемента дерева разбора (или АСТ) хранится позиция его начала и позиция его конца. Так как дерево разбора и АСТ получаются по исходникам, то выдерживается правило, что диапазоны не пересекаются, а более мелкие диапазоны вложены в более крупные.

При этом поиск тупым обходом такого дерева получается очень эффективным. Мы просто проверяем пересекается ли позиция с диапазоном и входим в эту ветку, если пересекается. Далее проделываем тоже самое рекурсивно пока не находим самую листовую ветку.

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

Если диапазоны не строго вложены (как с позициями у нас) можно ввести фиктивные узлы хранящие пересекающиеся подузлы. Твой вариант можно представить так:

[ 5, 15] -> Царь
[25, 50]
  [25, 40] -> Чурка
  [35, 50] -> Медведь

Здесь отступ описывает вложенность узлов.

Теперь поиск выливается в банальный перебор корневых веток с заходом в те подветки которые пересекаются с искомым диапазоном.

За счет сортировки вложенных веток можно получить с логарифмической сложностью.

Кода будет не мало, но за часа 3 он пишется без проблем.

Здравствуйте, SergASh, Вы писали:

SAS>Например, словарь такой:
SAS>

SAS>[ 5, 15] -> Царь
SAS>[35, 50] -> Медведь
SAS>[25, 40] -> Чурка
SAS>

SAS>Подаем на вход [10, 30], получаем
SAS>

SAS>[ 5, 15] -> Царь
SAS>[25, 40] -> Чурка
SAS>

у нас в Nitra

Автор: VladD2
Дата: 18.12.15

похожим образом хранятся позиции в тексте. Для каждого элемента дерева разбора (или АСТ) хранится позиция его начала и позиция его конца. Так как дерево разбора и АСТ получаются по исходникам, то выдерживается правило, что диапазоны не пересекаются, а более мелкие диапазоны вложены в более крупные.

При этом поиск тупым обходом такого дерева получается очень эффективным. Мы просто проверяем пересекается ли позиция с диапазоном и входим в эту ветку, если пересекается. Далее проделываем тоже самое рекурсивно пока не находим самую листовую ветку.

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

Если диапазоны не строго вложены (как с позициями у нас) можно ввести фиктивные узлы хранящие пересекающиеся подузлы. Твой вариант можно представить так:

[ 5, 15] -> Царь
[25, 50]
  [25, 40] -> Чурка
  [35, 50] -> Медведь

Здесь отступ описывает вложенность узлов.

Теперь поиск выливается в банальный перебор корневых веток с заходом в те подветки которые пересекаются с искомым диапазоном.

За счет сортировки вложенных веток можно получить логарифмическую сложность.

Кода будет не мало, но часа за 3 он пишется без проблем.