Википедия:Кандидаты в хорошие статьи/6 апреля 2020
На этой странице обсуждаются кандидаты в хорошие статьи русской Википедии. |
Правила обсуждения
|
Статья про незаслуженно малопопулярную (по сравнению с суффиксное дерево) строковую структуру данных. Понемногу расширял с лета, надеюсь довести до ИС, но решил сперва всё же сюда. Ещё вижу потенциал для расширения, но уже сейчас, на мой взгляд, статья достаточно подробно раскрывает основные моменты. Статья была на рецензировании. adamant.pwn — contrib/talk 16:37, 6 апреля 2020 (UTC)
За[править код]
- За. Грандиозно! Если всё остальное читатель и не поймёт, то благодаря пояснениям в таблице с рисунками «Построение суффиксного автомата для слова abbcbc» есть шанс на какое-то интуитивное понимание. Возвращаясь к этой центральной, на мой взгляд, последовательности иллюстраций, гвоздю статьи в разделе Изменение переходов и суффиксных ссылок… В левой или верхней части каждой ячейки у нас «суффиксный автомат», а в правой или нижней части — «дерево суффиксных ссылок». Читателю будет легче воспринять эту разницу, если все автоматы или все деревья в этой таблице будут другого, не чёрного цвета. Например, автоматы чёрные, а деревья зелёные или коричневые. --Andrew Krizhanovsky (обс.) 04:34, 11 мая 2020 (UTC)
Против[править код]
Комментарии[править код]
- Выглядит неплохо. Только почему б авторов в верхнем шаблоне не вписать шаблоном НП5? — Muhranoff (обс.) 08:58, 7 апреля 2020 (UTC)
- Потому что они подгружаются с викидаты… adamant.pwn — contrib/talk 10:39, 7 апреля 2020 (UTC)
- Так потому и подгружаются, что не вписаны. — Muhranoff (обс.) 14:33, 7 апреля 2020 (UTC)
- Ну, по мне викификация на викиданные это не такая уж и проблема, но так и быть — вписал через iw5. adamant.pwn — contrib/talk 16:22, 7 апреля 2020 (UTC)
- Так потому и подгружаются, что не вписаны. — Muhranoff (обс.) 14:33, 7 апреля 2020 (UTC)
- Потому что они подгружаются с викидаты… adamant.pwn — contrib/talk 10:39, 7 апреля 2020 (UTC)
- Историю лучше переименовать в исторический очерк и поместить ближе к концу. В начале статьи вообще непонятно о чём речь, имена и даты не имеют смысла. — Zanka (обс.) 11:57, 7 апреля 2020 (UTC)
- Ну не знаю, вроде бы обычно такие разделы всё таки идут в начале статьи и называются «история»… См. Алгоритм Евклида, например. Или тот же Алгоритм Шрайера — Симса. adamant.pwn — contrib/talk 12:09, 7 апреля 2020 (UTC)
- В определении слова неясно предназначение k (в смысле ясно, но оно там лишнее, в формуле слова k нет). — Zanka (обс.) 11:57, 7 апреля 2020 (UTC)
- Убрал. adamant.pwn — contrib/talk 12:36, 7 апреля 2020 (UTC)
- В конце раздела Основные обозначения стоит точка с запятой, а перед словом соответственно не хватает запятой. — Zanka (обс.) 11:57, 7 апреля 2020 (UTC)
- Заменил на точку. Зачем перед словом соответственно запятая не понял, это ведь не переход от одной части предложения к другой... adamant.pwn — contrib/talk 12:36, 7 апреля 2020 (UTC)
- Формулировку кортежа лучше дать в другом порядке, для тех кто в математику заглядывает изредка, как я, а не находится в ней 24/7. Сначала обозначить все элементы, а потом сказать, что они задают суффиксный автомат. В чистом виде поменять местами предложени не получится, нужно чуть-чуть больше править. — Zanka (обс.) 11:57, 7 апреля 2020 (UTC)
- Попробовал расписать подробнее. Так лучше? adamant.pwn — contrib/talk 12:36, 7 апреля 2020 (UTC)
- Непонятно, в каком месте заканчивается конечный автомат и начинается суффиксный. Ну то есть начиная с какого-то места говорится уже про суффиксный автомат, но определение непонятно. — Zanka (обс.) 11:57, 7 апреля 2020 (UTC)
- Попробовал выделить более явно. Про суффиксный автомат начинаем говорить с «В таких обозначениях, суффиксный автомат — это минимальный ДКА…». adamant.pwn — contrib/talk 12:36, 7 апреля 2020 (UTC)
- В состоянии автомата появляется буква R, неопределённая ранее. — Zanka (обс.) 11:57, 7 апреля 2020 (UTC)
- Речь про ? Ну, она соответствует слову «right», это следует явно прописать? adamant.pwn — contrib/talk 12:36, 7 апреля 2020 (UTC)
- Правый конец и правый контекст - это одно и то же или нет? Если нет, то что тогда правый конец? В любом случае хорошо бы это уточнить в статье. — Zanka (обс.) 11:57, 7 апреля 2020 (UTC)
- Исправил на «правую позицию» и добавил про это в «основные обозначения». Теперь понятнее? adamant.pwn — contrib/talk 12:36, 7 апреля 2020 (UTC)
- Последняя формула первой леммы меня смущает. Там вроде как длина слова, как она может принадлежать множеству правых концов? Вроде как размерности разные получаются. — Zanka (обс.) 11:57, 7 апреля 2020 (UTC)
- Всё в порядке -- правая позиция вхождения это число, разность и длины слова -- тоже. adamant.pwn — contrib/talk 12:36, 7 апреля 2020 (UTC)
- Там где "суффиксные ссылки образуют дерево", не знаю, есть ли у нас статьи, но дерево, вершины и рёбра хорошо бы викифицировать. И в "такие что" должна быть запятая. — Zanka (обс.) 11:57, 7 апреля 2020 (UTC)
- Викифицировал. adamant.pwn — contrib/talk 12:37, 7 апреля 2020 (UTC)
Я попробую дальше почитать, но уровень математики не мой, могут быть слишком глупые вопросы. — Zanka (обс.) 11:57, 7 апреля 2020 (UTC)
Алгоритм[править код]
Напишу здесь несколько пожеланий к разделу "Алгоритм".
- Предлагаю дать название алгоритму и разделу. То есть не просто "Алгоритм", а например "Алгоритм построения суффиксного автомата".
- В дополнение к ссылке "Crochemore, Hancart, 1997, pp. 31—36" можно сослаться на конкретную страницу PDF файла с помощью конструкции #page=34 вот так: [1].
Правильно я понял, что Ваш алгоритм в разделе «Алгоритм» — это Ваша интерпретация псевдокода Fig. 7.4 и Fig. 7.5? Если это так, то…
3) Попробуйте, пожалуйста, привести (кроме текстового описания и программы на С++, которые уже есть в разделе) также и псевдокод. Псевдокод популярен, поскольку он позволяет компактно описать то, что текстом выливается в целую портянку или простыню :) В идеале нумерация строк псевдокода совпадает с нумерацией текстового алгоритма.
4) Укажите, пожалуйста, входные параметры и результат алгоритма (что возвращает алгоритм). У них (Fig. 7.4 и Fig. 7.5) это указано.
Третье пожелание самое сложное в реализации и самое важное, чтобы читателей, понявших статью, стало на N+1 больше :) --Andrew Krizhanovsky (обс.) 15:27, 26 апреля 2020 (UTC)
- Сделал, за исключением прямой сноски на страницу. Ссылка с
#page=34
, кажется, не очень сочетается с форматом {{sfn-текст}}, который используется в статье для оформления сносок, так как они могут напрямую ссылаться только на развёрнутый текст в разделе «Литература». adamant.pwn — contrib/talk 18:51, 26 апреля 2020 (UTC) - В «префиксом, суффиксом и подсловом» — может, переставить в альфа-бета-гамма, а то глаз спотыкается?«Формально, детерминированный конечный автомат» — разве в разделе есть что-то от детерминированности?К моменту «важное утверждение о минимальных автоматах» нигде не определяется, что такое минимальный автомат. Викизавр (обс.) 17:35, 30 апреля 2020 (UTC)
- Исправил определение, чтоб соответствовало детерминированности, минимальный автомат определил. Альфа-бета-гамма здесь нежелательны, хочется сделать акцент на префиксе и суффиксе. adamant.pwn — contrib/talk 19:49, 30 апреля 2020 (UTC)
Лемма, определяющая взаимно-однозначное соответствие[править код]
Цитата из статьи:
Это позволяет сформулировать следующую лемму, определяющую взаимно-однозначное соответствие между правым контекстом слова и множеством позиций его вхождений в в качестве подслова:
Пусть — множество правых позиций вхождений в .
Между элементами множеств и есть следующее взаимно однозначное соответствие:
- Если , то ;
- Если , то .
Конец цитаты.
Хочу понять лемму. Понял, что endpos(w) — это множество чисел, позиций слова w в строке S. Не понял, что такое l и r в первой строке леммы. (l и r понял).
Хорошо бы примерчик в статью. Например, пусть S="кот ел антрекот" (15 символов), w="кот". Чему тогда равно по этой лемме endpos("кот")=? и ? --Andrew Krizhanovsky (обс.) 15:27, 26 апреля 2020 (UTC)
- (если нумерация символов в строке идёт с единицы). Правильно? Осталось с разобраться... --Andrew Krizhanovsky (обс.) 15:35, 26 апреля 2020 (UTC)
- Добавил пример и уточнение. adamant.pwn — contrib/talk 19:00, 26 апреля 2020 (UTC)
- Отлично! Теперь хочется довести пример до логического конца, то есть приведём пример для последних двух строчек леммы. Вы дали чёткий и ясный пример:
Например, для слова и его подслова выполнено и . (и неформальное пояснение)
Предлагаю вначале этого примера написать: (индекс указывает номер символа).
Продолжаем пример. Если , то положим .
Если , то положим .
Буду признателен, если Вы простите мне, что я так разжёвываю материал, который Вам очевиден. Мне кажется, что рядовым читателям с такими примерами будет понятнее.
По оформлению. Вот бы разместить параллельно лемму и пример. Это компактно и наглядно. Попробую сделать так.
Лемма | Пример, дано слово и подслово |
---|---|
Пусть — множество правых позиций вхождений в . |
|
Между элементами множеств и есть следующее взаимно однозначное соответствие: | |
* Если , то ; |
Если , то положим . |
* Если , то . |
Если , то положим . |
(Мелочь: "взаимно однозначное" сейчас в статье встречается раздельно и через дефис. Выберите что-то одно, пожалуйста.)
Я позволил себе в заголовке таблицы дать лемме название в виде формулы. Не настаиваю на таком названии.
Если содержательно согласны с этой таблицей, то для оформления таблицы нужно сообразить, как убрать горизонтальные линии в таблице, чтобы и лемма, и пример были целостными. Можно фон убрать у леммы. Можно убрать линии таблицы вокруг столбца с примером, оставить рамку только вокруг леммы, как было в оригинале. --Andrew Krizhanovsky (обс.) 07:46, 27 апреля 2020 (UTC)
- Дополнил чуть более подробным описанием. Думаю, параллельно отображать лемму и пример не следует, т. к. такое оформление не используется с другими утверждениями, обрамлёнными в {{теорема}}. adamant.pwn — contrib/talk 18:09, 27 апреля 2020 (UTC)
- Спасибо, что дополнили пример.
- Жаль, что не взяли параллельный пример к лемме. Аргумент за единообразие всех теорем понятен, но мы можем и для других лемм/теорем подумать над примерами :) --Andrew Krizhanovsky (обс.) 12:32, 28 апреля 2020 (UTC)
Структурные свойства состояний суффиксного автомата и его слов[править код]
Цитата:
Из этого следует ряд структурных свойств состояний суффиксного автомата и слов, которые ими принимаются. Пусть , тогда:
- Если у и есть хотя бы один общий элемент , то — суффикс и, как следствие, и ;
Конец цитаты.
Предлагаю такой текст для примера:
В качестве примера возьмём то же , положим (чтобы использовать предыдущий пример) и , то получим:
- ;
- (см. предыдущий пример);
- ;
Здесь общим элементом и является , при этом является суффиксом .
Конец текста для примера.
Замечания:
- Не слишком ли простой получился пример и слишком короткое (из одного символа)? Хотя, может, пример и должен быть простым.
- Для меня чудо и фокус состоит в том, что при общем иксе, оказалось суффиксом . Доказывается ли это строго? Или это очевидно? --Andrew Krizhanovsky (обс.) 13:24, 28 апреля 2020 (UTC)
- Давайте сразу уточним — вы сейчас хотите оснастить примером все утверждения в тексте? По поводу последнего — если у двух строк совпадает одна из правых позиций вхождений в строку, то более короткая является суффиксом более длинной. В общем, да, это очевидное свойство. Это примерно равносильно тому, что если и являются суффиксами третьей строки , то одна из них — суффикс другой. Возможно, пропущенная мысль тут в том, что если у и есть общий элемент, то он есть и у и , по доказанному выше. adamant.pwn — contrib/talk 13:51, 28 апреля 2020 (UTC)
- Мне думается, что примеры облегчают понимание читателям. Если бы тема и текст были проще, рецензентов было бы куда больше. Позволю себе пригласить к чтению статьи математика @Участник:Tosha. Чегой-то я кроме Занки и Тоши не вспоминаю математиков в рувики, хотя они, конечно, есть и просто ждут приглашения сюда (я сам случайно на эту номинацию наткнулся, к счастью или несчастью номинатора).
- adamant.pwn, Вы пишите про возможную "пропущенную мысль". Может её стоит добавить в статью со ссылкой на предыдущую лемму? --Andrew Krizhanovsky (обс.) 07:40, 30 апреля 2020 (UTC)
- Мне просто кажется, что было бы удобнее и быстрее сразу обозначить все места, где хочется иметь более подробные пояснения, чтоб работать с ними параллельно, а не последовательно. А приглашение к рецензированию — оно на Проект:Математика висит, только мне кажется, что в нашем разделе обычно другими разделами математики интересуются, потому и данная номинация не очень популярна. В целом, я в последнее время стараюсь не очень усердствовать с примерами в статьях, так как это может вызвать реакция вида «пример — это оригинальное исследование» или «нет в АИ — не нужно нести в статью» со стороны ряда участников. А в статусных проектах эти примеры ещё и образуют абзацы без сносок, что здесь вообще как красная тряпка… adamant.pwn — contrib/talk 07:51, 30 апреля 2020 (UTC)
- Аргумент про опасение обвинений из-за примеров понял. Думаю, что случай с кандидатами в статусные статьи особый в том, что есть обсуждение и решение нескольких участников. Если продолжить линию опасений, то придётся отказаться от исходных кодов, иллюстрирующих алгоритмы, если их нет в АИ.
- Параллельно, к сожалению, не могу. Вы уже догадались, что у меня в голове однопроцессорная устаревшая модель :) Поэтому я пишу замечания по ходу чтения текста. --Andrew Krizhanovsky (обс.) 08:04, 30 апреля 2020 (UTC)
- Да, исходный код на самом деле нежелателен, особенно если в статье есть псевдокод, я его убрал. adamant.pwn — contrib/talk 19:56, 30 апреля 2020 (UTC)
- Дополнил. adamant.pwn — contrib/talk 09:36, 30 апреля 2020 (UTC)
- Спасибо! --Andrew Krizhanovsky (обс.) 12:49, 30 апреля 2020 (UTC)
Ох уж эта гамма[править код]
Вы пишите третье структурное свойство:
- Если и — суффикс , такой что , то .
А вы можете привести такой пример гаммы не равной бете по длине, чтобы ? Мне кажется, что если , то . --Andrew Krizhanovsky (обс.) 13:24, 28 апреля 2020 (UTC)
- Да, конечно. Строка , подстроки , и . Здесь . adamant.pwn — contrib/talk 13:45, 28 апреля 2020 (UTC)
- Правильно я понял, что если исключить пустое слово как особый случай, то привести пример навскидку для третьего структурного свойства не получится? --Andrew Krizhanovsky (обс.) 06:52, 30 апреля 2020 (UTC)
- Неправильно. , но — те же самые. Тогда . adamant.pwn — contrib/talk 07:13, 30 апреля 2020 (UTC)
- Спасибо! --Andrew Krizhanovsky (обс.) 07:41, 30 апреля 2020 (UTC)
- Правильно я понял, что если исключить пустое слово как особый случай, то привести пример навскидку для третьего структурного свойства не получится? --Andrew Krizhanovsky (обс.) 06:52, 30 апреля 2020 (UTC)
Приглашение для математиков[править код]
Уважаемые коллеги, @Agor153, @Arventur, @colt_browning, @Irina Gelbukh, @Jumpow, @Sim3331621. Я видел, что вы редактировали статьи по математике. Поэтому приглашаю к рецензированию статьи Суффиксный автомат. Если такие уведомления неинтересны, напишите мне, пожалуйста. Постараюсь больше не беспокоить. --Andrew Krizhanovsky (обс.) 07:57, 30 апреля 2020 (UTC)
Левое расширение[править код]
Цитата:
Левым расширением строки называют самую длинную строку , имеющую тот же правый контекст, что и . Длину самой длинной строки, принимаемой состоянием , обозначают как .
- Например, для слова и правого контекста имеем, что подслово нельзя расширить, не потеряв элементы правого контекста, поэтому .
Верно ли я понял, как вычисляют длину q? --Andrew Krizhanovsky (обс.) 18:02, 1 мая 2020 (UTC)
- Нет, в данном случае мы смотрим на все слова, у которых правый контекст равен . Нас интересует длина наибольшего такого слова, то есть, . adamant.pwn — contrib/talk 18:10, 1 мая 2020 (UTC)
- Теперь понял. Спасибо! --Andrew Krizhanovsky (обс.) 13:36, 2 мая 2020 (UTC)
Пример построения[править код]
В статье на русском языке [2] есть раздел "Пример построения". Думаю, что подобный раздел в нашей статьи был бы уместен и полезен. Возможно, для другой строки. По оформлению вполне устраивает таблица: слева рисунок и справа описание для каждого шага. --Andrew Krizhanovsky (обс.) 17:12, 4 мая 2020 (UTC)
- Мне бы не очень хотелось занимать таким примером много вертикального места. Для иллюстрации, мне кажется, более-менее достаточно одного отдельного шага, изображённого на «Изменения в суффиксных структурах при приписывании одного символа». Меня бы устроило оформить это в виде встроенного слайд-шоу или таблицы с вкладками, но я не уверен, как это наилучшим образом технически реализовать. adamant.pwn — contrib/talk 08:35, 8 мая 2020 (UTC)
- Таблица не будет занимать места, если она по умолчанию свёрнута. Вот документация: Википедия:Таблицы#Сворачиваемая. --Andrew Krizhanovsky (обс.) 18:36, 8 мая 2020 (UTC)
- Нет, так она будет заниматься много места если развернуть. Сделал под это дело Шаблон:Слайд-шоу. Осталось понаделать картинок… adamant.pwn — contrib/talk 18:32, 9 мая 2020 (UTC)
- Добавил. adamant.pwn — contrib/talk 23:13, 9 мая 2020 (UTC)
- Таблица не будет занимать места, если она по умолчанию свёрнута. Вот документация: Википедия:Таблицы#Сворачиваемая. --Andrew Krizhanovsky (обс.) 18:36, 8 мая 2020 (UTC)
Итог[править код]
Статья требованиям соответствует, проведена большая работа по замечаниям. Статус присвоен, рекомендую номинировать на КИС. — Zanka (обс.) 20:50, 16 мая 2020 (UTC)