Вопрос: есть у нас интерес в написании своего САБЖа и добавлении его в либу?
А то мне тут понадобился для решения всяких мозголомных задачек, а ни одной приличной реализации под .NET я не нашел. Подумываю свою запилить.
API для последующего использования после создания дерева пока нет. Буду его прикручивать второй очередью.
Кусок функционала вынесен в абстрактную базу, чтобы не дублировать код между SuffixTree и SuffixTreeNaive. Второе используется как простая референс-реализация для тестирования основной. В принципе, можно, и кодогенератор под это заюзать, чтобы не плодить базовые классы для внутреннего использования.
Текущую реализацию я успешно использовал для решения вот этой задачки: https://www.hackerrank.com/challenges/string-function-calculation.
Просто отсабклассил SuffixTree, и использовал внутреннее представления дерева (в принципе, под нее приличное паблик API все равно сложно придумать).
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, Lexey, Вы писали:
AVK>Кстати, о птичках: неплохо было бы тогда и interval tree на базе наших интервалов сделать.
Актуально? Хотел бы реализовать. Естественно с меня соблюдение code style и т.п...
Здравствуйте, Lexey, Вы писали:
L>https://github.com/rsdn/CodeJam/pull/16/files L>API для последующего использования после создания дерева пока нет. Буду его прикручивать второй очередью.
, код нравится. Из предложений пока только мелочь — поменять оформление полей — префикс (_) в начале имени у нас вроде ставится
L>Кусок функционала вынесен в абстрактную базу, чтобы не дублировать код между SuffixTree и SuffixTreeNaive. Второе используется как простая референс-реализация для тестирования основной. В принципе, можно, и кодогенератор под это заюзать, чтобы не плодить базовые классы для внутреннего использования.
Разделение на классы я бы трогал в последнюю очередь — сначала сделать полезный функционал, затем покрыть тестами, затем уже менять. На сейчас разделение выглядит абсолютно правильным, т.к. во-первых позволяет аккуратно всё протестировать, во-вторых позволяет разбить сложный код на несколько частей попроще. Если не хочется, чтобы эти детали вылезали при автодополнении — просто спрятать базовый класс в отдельный namespace, да и всё.
Здравствуйте, Sinix, Вы писали:
S>Здравствуйте, Lexey, Вы писали:
L>>Пожелания по сценариям приветствуются. У меня пока есть один готовый — поиск подстроки, которая чаще всего встречается в исходной строке.
S>Вот что-то я не вспомню сходу, чтоб в реальных сценариях "произвольные" suffix tree нужны были, их же несколько разновидностей емнип.
У самой структуры Suffix Tree, вроде, только одна разновидность.
S>Чего конкретно делать будем — Ахо-Корасика, Укконена или упрощённый Вейнера?
Это алгоритмы построения. Я думал Укконена сделать. Сейчас у меня уже есть простая реализация, котороя скорее всего соответствует Вейнеру. Я ее думал для тестов нормального алгоритма юзать.
S>Api как минимум Add, IndexesOf, Contains, для полного счастья можно простенькие маски прилепить.
Add чего?
Contains понятно.
IndexesOf что возвращать должно? Список индексов или энумератор?
Над масками думать нужно.
Cобственно Suffix Tree там только 2 вижу — обычное и lazy. Остальное — tries, suffix array'и и гибриды.
S>Ну ок, как понял, будет простое статическое suffix tree с Укконеном?
Угу.
S>Тогда add — нафиг, проще дерево перестроить. Contains — ок. IndexesOf — я бы сделал массив или список, на твоё усмотрение.
ОК.
S>Главное чтоб индексы отсортированными были, так множество сценариев типа тех же масок проще сделать.
Придется явно сортировать, скорее всего. Не уверен, что это хорошая идея.
Здравствуйте, AndrewVK, Вы писали:
AVK>По идее довольно полезная вещь, особенно если добавить к ней некоторое количество готовых сценариев применения, а не просто голую структуру засунуть.
Пожелания по сценариям приветствуются. У меня пока есть один готовый — поиск подстроки, которая чаще всего встречается в исходной строке.
Здравствуйте, Lexey, Вы писали:
L>Пожелания по сценариям приветствуются. У меня пока есть один готовый — поиск подстроки, которая чаще всего встречается в исходной строке.
Вот что-то я не вспомню сходу, чтоб в реальных сценариях "произвольные" suffix tree нужны были, их же несколько разновидностей емнип.
Чего конкретно делать будем — Ахо-Корасика, Укконена или упрощённый Вейнера?
Api как минимум Add, IndexesOf, Contains, для полного счастья можно простенькие маски прилепить.
Ну ок, как понял, будет простое статическое suffix tree с Укконеном?
Тогда add — нафиг, проще дерево перестроить. Contains — ок. IndexesOf — я бы сделал массив или список, на твоё усмотрение.
Главное чтоб индексы отсортированными были, так множество сценариев типа тех же масок проще сделать.
Здравствуйте, Lexey, Вы писали:
L>А то мне тут понадобился для решения всяких мозголомных задачек, а ни одной приличной реализации под .NET я не нашел. Подумываю свою запилить.
Лучше запили suffix array. На большинстве реальных задач будет быстрее или как минимум не медленнее, и потребление памяти на порядок меньше.
Здравствуйте, consign, Вы писали:
C>Лучше запили suffix array. На большинстве реальных задач будет быстрее или как минимум не медленнее, и потребление памяти на порядок меньше.
Может быть запилю после ST. Сечас мне больше оно интересно.
Здравствуйте, Lexey, Вы писали:
L>Придется явно сортировать, скорее всего. Ну уверен, что это хорошая идея.
Ну и ок, тогда не будем увлекаться и начнём с работающего варианта, поломать всегда успеем
Здравствуйте, Sinix, Вы писали:
S>, код нравится. Из предложений пока только мелочь — поменять оформление полей — префикс (_) в начале имени у нас вроде ставится
Выкроил сегодня время и написал методы:
All() — энумератор всех суффиксов,
Contains(string) — проверка, если подстрока в дереве
ContainsSuffix(string) — проверка, если суффикс в дереве,
StartingWith(string) — энумератор всех суффиксов, начинающихся со строки
(Это вместо предложенного ранее IndexOf, ибо в случае дерева с несколькими строками просто IndexOf лишен смысла. Внутри структурки Suffix возвращается в том числе и индекс внутри исходной строки).
Позже постараюсь сделать варианты ContainsSuffix и StartingWith с масками (Contains не вижу смысла делать, ибо это будет тоже самое, что ContainsSuffix для маски с * в конце).
Здравствуйте, Spinifex, Вы писали:
AVK>>Кстати, о птичках: неплохо было бы тогда и interval tree на базе наших интервалов сделать. S>Актуально? Хотел бы реализовать. Естественно с меня соблюдение code style и т.п...
Интересно конечно. У меня есть реализация составных диапазонов, раз интерес есть, попробую закинуть на днях.
Она не оптимизирована по производительности (упор был на корректность работы), но поддерживает все основные операции: дополнение к диапазону / пересечение / объединение / получение отрезков (разбиение по границам диапазонов).
Всё по стоимости O(n), требует сортировки при создании диапазона, но поскольку за 4 года нам так и не потребовалось никогда работать больше чем с парой десятков поддиапазонов, никто не заморачивался.
, код нравится. Из предложений пока только мелочь — поменять оформление полей — префикс (_) в начале имени у нас вроде ставится 
