Википедия:Кандидаты в хорошие статьи/6 апреля 2020

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Здесь находятся завершившиеся обсуждения. Просьба не вносить изменений.

Статья про незаслуженно малопопулярную (по сравнению с суффиксное дерево) строковую структуру данных. Понемногу расширял с лета, надеюсь довести до ИС, но решил сперва всё же сюда. Ещё вижу потенциал для расширения, но уже сейчас, на мой взгляд, статья достаточно подробно раскрывает основные моменты. Статья была на рецензировании. adamant.pwncontrib/talk 16:37, 6 апреля 2020 (UTC)[ответить]

За[править код]

  1. (+) За. Грандиозно! Если всё остальное читатель и не поймёт, то благодаря пояснениям в таблице с рисунками «Построение суффиксного автомата для слова abbcbc» есть шанс на какое-то интуитивное понимание. Возвращаясь к этой центральной, на мой взгляд, последовательности иллюстраций, гвоздю статьи в разделе Изменение переходов и суффиксных ссылок… В левой или верхней части каждой ячейки у нас «суффиксный автомат», а в правой или нижней части — «дерево суффиксных ссылок». Читателю будет легче воспринять эту разницу, если все автоматы или все деревья в этой таблице будут другого, не чёрного цвета. Например, автоматы чёрные, а деревья зелёные или коричневые. --Andrew Krizhanovsky (обс.) 04:34, 11 мая 2020 (UTC)[ответить]

Против[править код]

Комментарии[править код]

Я попробую дальше почитать, но уровень математики не мой, могут быть слишком глупые вопросы. — Zanka (обс.) 11:57, 7 апреля 2020 (UTC)[ответить]

Алгоритм[править код]

Напишу здесь несколько пожеланий к разделу "Алгоритм".

  1. Предлагаю дать название алгоритму и разделу. То есть не просто "Алгоритм", а например "Алгоритм построения суффиксного автомата".
  2. В дополнение к ссылке "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.pwncontrib/talk 18:51, 26 апреля 2020 (UTC)[ответить]
  • В «префиксом, суффиксом и подсловом» — может, переставить в альфа-бета-гамма, а то глаз спотыкается?
    «Формально, детерминированный конечный автомат» — разве в разделе есть что-то от детерминированности?
    К моменту «важное утверждение о минимальных автоматах» нигде не определяется, что такое минимальный автомат. Викизавр (обс.) 17:35, 30 апреля 2020 (UTC)[ответить]
    • Исправил определение, чтоб соответствовало детерминированности, минимальный автомат определил. Альфа-бета-гамма здесь нежелательны, хочется сделать акцент на префиксе и суффиксе. adamant.pwncontrib/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)[ответить]
  • Отлично! Теперь хочется довести пример до логического конца, то есть приведём пример для последних двух строчек леммы. Вы дали чёткий и ясный пример:
Например, для слова  и его подслова  выполнено  и . (и неформальное пояснение)

Предлагаю вначале этого примера написать: (индекс указывает номер символа).

Продолжаем пример. Если , то положим .

Если , то положим .

Буду признателен, если Вы простите мне, что я так разжёвываю материал, который Вам очевиден. Мне кажется, что рядовым читателям с такими примерами будет понятнее.

По оформлению. Вот бы разместить параллельно лемму и пример. Это компактно и наглядно. Попробую сделать так.

Лемма
Лемма Пример, дано слово и подслово
Пусть — множество правых позиций вхождений в .

Между элементами множеств и есть следующее взаимно однозначное соответствие:
* Если , то ;

Если , то положим .

* Если , то .

Если , то положим .

(Мелочь: "взаимно однозначное" сейчас в статье встречается раздельно и через дефис. Выберите что-то одно, пожалуйста.)

Я позволил себе в заголовке таблицы дать лемме название в виде формулы. Не настаиваю на таком названии.

Если содержательно согласны с этой таблицей, то для оформления таблицы нужно сообразить, как убрать горизонтальные линии в таблице, чтобы и лемма, и пример были целостными. Можно фон убрать у леммы. Можно убрать линии таблицы вокруг столбца с примером, оставить рамку только вокруг леммы, как было в оригинале. --Andrew Krizhanovsky (обс.) 07:46, 27 апреля 2020 (UTC)[ответить]

  • Дополнил чуть более подробным описанием. Думаю, параллельно отображать лемму и пример не следует, т. к. такое оформление не используется с другими утверждениями, обрамлёнными в {{теорема}}. adamant.pwncontrib/talk 18:09, 27 апреля 2020 (UTC)[ответить]
  • Спасибо, что дополнили пример.
  • Жаль, что не взяли параллельный пример к лемме. Аргумент за единообразие всех теорем понятен, но мы можем и для других лемм/теорем подумать над примерами :) --Andrew Krizhanovsky (обс.) 12:32, 28 апреля 2020 (UTC)[ответить]

Структурные свойства состояний суффиксного автомата и его слов[править код]

Цитата:

Из этого следует ряд структурных свойств состояний суффиксного автомата и слов, которые ими принимаются. Пусть , тогда:

  • Если у и есть хотя бы один общий элемент , то — суффикс и, как следствие, и ;

Конец цитаты.

Предлагаю такой текст для примера:

В качестве примера возьмём то же , положим (чтобы использовать предыдущий пример) и , то получим:

  • ;
  • (см. предыдущий пример);
  • ;

Здесь общим элементом и является , при этом является суффиксом .

Конец текста для примера.

Замечания:

  1. Не слишком ли простой получился пример и слишком короткое (из одного символа)? Хотя, может, пример и должен быть простым.
  2. Для меня чудо и фокус состоит в том, что при общем иксе, оказалось суффиксом . Доказывается ли это строго? Или это очевидно? --Andrew Krizhanovsky (обс.) 13:24, 28 апреля 2020 (UTC)[ответить]
  • Давайте сразу уточним — вы сейчас хотите оснастить примером все утверждения в тексте? По поводу последнего — если у двух строк совпадает одна из правых позиций вхождений в строку, то более короткая является суффиксом более длинной. В общем, да, это очевидное свойство. Это примерно равносильно тому, что если и являются суффиксами третьей строки , то одна из них — суффикс другой. Возможно, пропущенная мысль тут в том, что если у и есть общий элемент, то он есть и у и , по доказанному выше. adamant.pwncontrib/talk 13:51, 28 апреля 2020 (UTC)[ответить]
  • Мне думается, что примеры облегчают понимание читателям. Если бы тема и текст были проще, рецензентов было бы куда больше. Позволю себе пригласить к чтению статьи математика @Участник:Tosha. Чегой-то я кроме Занки и Тоши не вспоминаю математиков в рувики, хотя они, конечно, есть и просто ждут приглашения сюда (я сам случайно на эту номинацию наткнулся, к счастью или несчастью номинатора).
  • adamant.pwn, Вы пишите про возможную "пропущенную мысль". Может её стоит добавить в статью со ссылкой на предыдущую лемму? --Andrew Krizhanovsky (обс.) 07:40, 30 апреля 2020 (UTC)[ответить]
    • Мне просто кажется, что было бы удобнее и быстрее сразу обозначить все места, где хочется иметь более подробные пояснения, чтоб работать с ними параллельно, а не последовательно. А приглашение к рецензированию — оно на Проект:Математика висит, только мне кажется, что в нашем разделе обычно другими разделами математики интересуются, потому и данная номинация не очень популярна. В целом, я в последнее время стараюсь не очень усердствовать с примерами в статьях, так как это может вызвать реакция вида «пример — это оригинальное исследование» или «нет в АИ — не нужно нести в статью» со стороны ряда участников. А в статусных проектах эти примеры ещё и образуют абзацы без сносок, что здесь вообще как красная тряпка… adamant.pwncontrib/talk 07:51, 30 апреля 2020 (UTC)[ответить]
  • Аргумент про опасение обвинений из-за примеров понял. Думаю, что случай с кандидатами в статусные статьи особый в том, что есть обсуждение и решение нескольких участников. Если продолжить линию опасений, то придётся отказаться от исходных кодов, иллюстрирующих алгоритмы, если их нет в АИ.
  • Параллельно, к сожалению, не могу. Вы уже догадались, что у меня в голове однопроцессорная устаревшая модель :) Поэтому я пишу замечания по ходу чтения текста. --Andrew Krizhanovsky (обс.) 08:04, 30 апреля 2020 (UTC)[ответить]

Ох уж эта гамма[править код]

Вы пишите третье структурное свойство:

  • Если и — суффикс , такой что , то .

А вы можете привести такой пример гаммы не равной бете по длине, чтобы ? Мне кажется, что если , то . --Andrew Krizhanovsky (обс.) 13:24, 28 апреля 2020 (UTC)[ответить]

  • Да, конечно. Строка , подстроки , и . Здесь . adamant.pwncontrib/talk 13:45, 28 апреля 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.pwncontrib/talk 18:10, 1 мая 2020 (UTC)[ответить]

Пример построения[править код]

В статье на русском языке [2] есть раздел "Пример построения". Думаю, что подобный раздел в нашей статьи был бы уместен и полезен. Возможно, для другой строки. По оформлению вполне устраивает таблица: слева рисунок и справа описание для каждого шага. --Andrew Krizhanovsky (обс.) 17:12, 4 мая 2020 (UTC)[ответить]

  • Мне бы не очень хотелось занимать таким примером много вертикального места. Для иллюстрации, мне кажется, более-менее достаточно одного отдельного шага, изображённого на «Изменения в суффиксных структурах при приписывании одного символа». Меня бы устроило оформить это в виде встроенного слайд-шоу или таблицы с вкладками, но я не уверен, как это наилучшим образом технически реализовать. adamant.pwncontrib/talk 08:35, 8 мая 2020 (UTC)[ответить]

Итог[править код]

Статья требованиям соответствует, проведена большая работа по замечаниям. Статус присвоен, рекомендую номинировать на КИС. — Zanka (обс.) 20:50, 16 мая 2020 (UTC)[ответить]