Автоматы в современном мире - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:37:31Z

rollbackEdits.php mass rollback

185.220.101.2 в 04:04, 1 сентября 2022

2022-09-01T04:04:48Z

77.234.212.37: /* Несколько полезных оптимизаций на примере Haskell */

2018-03-15T07:37:08Z

‎Несколько полезных оптимизаций на примере Haskell

77.234.212.37: /* Несколько полезных оптимизаций на примере Haskell */

2018-03-15T07:34:58Z

‎Несколько полезных оптимизаций на примере Haskell

77.234.212.37: /* Несколько полезных оптимизаций на примере Haskell */

2018-03-15T07:32:27Z

‎Несколько полезных оптимизаций на примере Haskell

77.234.212.37: /* Построение НКА */

2018-03-15T07:27:47Z

‎Построение НКА

77.234.212.37: /* Построение НКА */

2018-03-15T07:27:03Z

‎Построение НКА

Ponomarev: /* ReDoS (regular expression denial of service) */

2018-03-14T21:02:26Z

‎ReDoS (regular expression denial of service)

Ponomarev: /* Несколько полезных оптимизаций на примере Haskell */

2018-03-14T20:59:22Z

‎Несколько полезных оптимизаций на примере Haskell

Ponomarev: /* Несколько полезных оптимизаций на примере Haskell */

2018-03-14T20:58:51Z

‎Несколько полезных оптимизаций на примере Haskell

← Предыдущая		Версия 16:37, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	== Реализация регулярных выражений в современных языках ==		== Реализация регулярных выражений в современных языках ==
	В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить НКА. Но после построения есть несколько вариантов:		В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить НКА. Но после построения есть несколько вариантов:

← Предыдущая		Версия 04:04, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	== Реализация регулярных выражений в современных языках ==		== Реализация регулярных выражений в современных языках ==
	В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить НКА. Но после построения есть несколько вариантов:		В настоящее время используется несколько различных подходов к реализации регулярных выражений. Всегда можно довольно просто построить НКА. Но после построения есть несколько вариантов:

@@ Строка 216: / Строка 216: @@
 * вместо <tex>\mathrm{Set Int}</tex> использовал <tex>\mathrm{Integer}</tex>, а также использовал битовые операции, в результате производительность выросла в <tex>5</tex> раз
 * использовал <tex>\mathrm{Word}</tex> вместо <tex>\mathrm{Integer}</tex>, ещё в <tex>8</tex> раз быстрее
-* а также использовал ByteString оптимизации, что увеличило производительность ещё <tex>3</tex> раза.
+* а также использовал <tex>\mathrm{ByteString}</tex> оптимизации, что увеличило производительность ещё <tex>3</tex> раза.
 В итоге его реализация оказалась всего в <tex>4</tex> раза медленнее grep. Но это не предел, у него получилось реализовать  параллельный конечный автомат<ref>[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf Data-Parallel Finite-State Machines]</ref> и сделать свою реализацию в <tex>1.5</tex> раза быстрее, чем grep.

@@ Строка 214: / Строка 214: @@
 Gabriel Gonzalez <ref>[https://begriffs.com/posts/2016-06-27-fast-haskell-regexes.html Gabriel Gonzalez {{---}} Regex in Haskell]</ref> реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в <tex>480</tex> раз медленнее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:
-* вместо Set Int использовал Integer, а также использовал битовые операции, в результате производительность выросла в <tex>5</tex> раз
+* вместо <tex>\mathrm{Set Int}</tex> использовал <tex>\mathrm{Integer}</tex>, а также использовал битовые операции, в результате производительность выросла в <tex>5</tex> раз
-* использовал Word вместо Integer, ещё в <tex>8</tex> раз быстрее
+* использовал <tex>\mathrm{Word}</tex> вместо <tex>\mathrm{Integer}</tex>, ещё в <tex>8</tex> раз быстрее
 * а также использовал ByteString оптимизации, что увеличило производительность ещё <tex>3</tex> раза.
 В итоге его реализация оказалась всего в <tex>4</tex> раза медленнее grep. Но это не предел, у него получилось реализовать  параллельный конечный автомат<ref>[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf Data-Parallel Finite-State Machines]</ref> и сделать свою реализацию в <tex>1.5</tex> раза быстрее, чем grep.

@@ Строка 213: / Строка 213: @@
 == Несколько полезных оптимизаций на примере Haskell ==
-Gabriel Gonzalez <ref>[https://begriffs.com/posts/2016-06-27-fast-haskell-regexes.html Gabriel Gonzalez {{---}} Regex in Haskell]</ref> реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в 480 раз медленнее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:
+Gabriel Gonzalez <ref>[https://begriffs.com/posts/2016-06-27-fast-haskell-regexes.html Gabriel Gonzalez {{---}} Regex in Haskell]</ref> реализовал алгоритм Томпсона на языке Haskell. В первоначальном варианте это алгоритм получился в <tex>480</tex> раз медленнее, чем grep на том же тесте, чтобы улучшить результат он предпринял ряд оптимизаций:
-* вместо Set Int использовал Integer, а также использовал битовые операции, в результате производительность выросла в 5 раз
+* вместо Set Int использовал Integer, а также использовал битовые операции, в результате производительность выросла в <tex>5</tex> раз
-* использовал Word вместо Integer, ещё в 8 раз быстрее
+* использовал Word вместо Integer, ещё в <tex>8</tex> раз быстрее
-* а также использовал ByteString оптимизации, что увеличило производительность ещё 3 раза.
+* а также использовал ByteString оптимизации, что увеличило производительность ещё <tex>3</tex> раза.
-В итоге его реализация оказалась всего в 4 раза медленнее grep. Но это не предел, у него получилось реализовать  параллельный конечный автомат<ref>[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf Data-Parallel Finite-State Machines]</ref> и сделать свою реализацию в 1.5 раза быстрее, чем grep.
+В итоге его реализация оказалась всего в <tex>4</tex> раза медленнее grep. Но это не предел, у него получилось реализовать  параллельный конечный автомат<ref>[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/asplos302-mytkowicz.pdf Data-Parallel Finite-State Machines]</ref> и сделать свою реализацию в <tex>1.5</tex> раза быстрее, чем grep.
 == ReDoS (regular expression denial of service) ==

@@ Строка 17: / Строка 17: @@
       '''state''' out1
       '''int''' lastlist
-Каждый <tex>\mathrm{state}</tex> представляет один из фрагментов НКА, зависящий от символа <tex>c<\tex>.
+Каждый <tex>\mathrm{state}</tex> представляет один из фрагментов НКА, зависящий от символа <tex>c</tex>.
 Данная реализация будет поддерживать постфиксную нотацию регулярного выражения. Допустим у нас есть функция <tex>\mathrm{re2post}</tex>, которая переписывает инфиксную форму регулярного выражения <tex>``a(bb)+a"</tex> в эквивалентную постфиксную вида <tex>``abb.+.a."</tex> (<tex>.</tex> используется в качестве разделителя). По мере сканирования постфиксного выражения, будем поддерживать стек вычисленных НКА фрагментов. Символы добавляют новый НКА фрагмент в стек, а операторы вынимают фрагменты и добавляют новые. Каждый фрагмент определяется стартовым состояние и исходящей стрелкой:
   '''struct''' frag:

@@ Строка 231: / Строка 231: @@
 Все эти выражения чувствительны к входной строке <tex>aaaaaaaaaaaaaaaaaaaaaaaaaa</tex>.
 Также вредоносные регулярные выражения были обнаружены в онлайн репозиториях.
-# [http://regexlib.com/REDetails.aspx?regexp_id=1757 RegExLib, id=1757 (email validation)] - '''выделенная''' часть является вредоносной<br /><code>^([a-zA-Z0-9])'''(([\-.]|[_]+)?([a-zA-Z0-9]+))*'''(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$</code>
+# RegExLib, email validation <ref>[http://regexlib.com/REDetails.aspx?regexp_id=1757 RegEx for email validation]</ref> {{---}} '''выделенная''' часть является вредоносной<br /><code>^([a-zA-Z0-9])'''(([\-.]|[_]+)?([a-zA-Z0-9]+))*'''(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$</code>
-# [http://www.owasp.org/index.php/OWASP_Validation_Regex_Repository OWASP Validation Regex Repository], Java Classname - '''выделенная''' часть является вредоносной<br /><code>^'''(([a-z])+.)+'''[A-Z]([a-z])+$</code>
+# OWASP Validation Regex Repository  <ref>[http://www.owasp.org/index.php/OWASP_Validation_Regex_Repository OWASP Validation Regex Repository]</ref>, Java Classname {{---}} '''выделенная''' часть является вредоносной<br /><code>^'''(([a-z])+.)+'''[A-Z]([a-z])+$</code>
 Эти два примера также чувствительны к входной строке <tex>aaaaaaaaaaaaaaaaaaaaaaaa</tex>.