webew
Войти » Регистрация
 
Алгоритмы

Алгоритм работы Punycode

26 декабря 2012, 8:07
Автор: platedz
Уже не знаю, где спросить, поэтому попробую здесь, может кто ответит.
Купил скрипт конструктор сайтов (construktor.info), но он не поддерживает русские домены.
Спецификацию RFC 3492 я почитал, хотя с английским довольно недружен, но тем не менее. Класс для создания Idn доменов я нашел, но как работает так и не понял. Объясните пожалуйста.
Т.е. я прекрасно понимаю, что из адреса нужно убрать все не ascii символы, спереди добавить xn-- а в конце -. А вот как после - символы кодируются не понял. Там что-то связано с конечным автоматом, но как работает конечный автомат я так и не разобрался. Т.ч. пояснение по принципу работы конечного автомата, особенно с каким нибудь простым примером, например на php или javascript тоже подойдет
Добавить комментарий
Отображение комментариев: Древовидное | Плоское

1234ru

Насчет алгоритма сказать ничего не могу, но, возможно, вы найдете полезную информацию по следующим ссылкам:
http://php.net/manual/en/ref.intl.idn.php
http://www.php.ru/forum/viewtopic.php?p=106632
То, что не убивает нас, делает нас инвалидами.
26.12.2012, 19:40
Ответить
NO USERPIC

platedz

Это не совсем то, что я хотел, тк. хотел я в первую очередь разобраться. Сейчас я застрял на таком понятии как конечный автомат, не могли бы Вы объяснить, что он из себя представляет. В частности в программировании а еще лучше в php
26.12.2012, 23:58
Ответить
NO USERPIC

rgbeast

Конечный автомат - специальный вид алгоритма, читающий входное слово последовательно по символам.
http://ru.wikipedia.org/wiki/%CA%EE%ED%E5%F7%ED%FB%E9_%E0%E2%F2%EE%EC%E0%F2

У конечного автомата может быть память (то есть переменные внутреннего состояния), но входное слова передается посимвольно и к памяти автомата не относится. Обработав каждый символ автомат меняет свое внутреннее состояние.

Вот иллюстративный пример (детали алгоритма не изучал). Пусть автомат имеет изначально две переменные X и n с начальным значением 0. Ему подается слово "корова". Он съедает букву к и переходит в состояние со значением X (допустим) равным 300, а n инкрементируется. Далее от съедает букву "о", n становится равным 2, а X какому-то числу. На выходе все слово съедено и остается значение X. Данное значение X переводится в буквенный код.
27.12.2012, 00:12
Ответить
NO USERPIC

platedz

Большое спасибо за ответ, но мне достаточно тяжело представить его практическое применение, и соответственно, алгоритм. Если сможете какой-нибудь короткий но достаточно емкий пример на php или js, как бы конечного автомата в принципе, то буду крайне признателен.
27.12.2012, 01:44
Ответить
NO USERPIC

platedz

Т.е. если я правильно понимаю, то алгоритм конечного автомата отличает наличие внутреннего состояния и внутренней памяти. Т.е. его отличие от обычного цикла или функции заключается в том, что выполнив какой-то алгоритм, скажем тот же цикл внутри функции он удерживает свое состояние.
Т.е. скажем есть некая функция, function а() в которой есть var В = 0;

$B = 0;
function a($var) {  
$C = 0;
for($i=0; $i<strlen($var); $i++) { $B++; C++; }

return C;
}
 


Запуская скажем какой-то код вызовем эти функцию дважды, передав ей какое-то значение. Скажем посчитаем количество букв в слове корова. и запишем это количество букв в переменную С.
function a("корова");
После чего С = 6; B = 6;
Также дополним эту переменную в В количеством всех символов, т.к. предположим В считает количество всех символов.
А затем передадим слово БЫК,
function a("Бык");
Вызвав функцию повторно, и получим в переменной
С = 3, B = 9, т.к. B сохранила свое внутреннее состояние.
В принципе здесь есть внутренняя память но в ней нет смысла, т.ч. думаю, считать ее конечным автоматом вследствии этого нельзя. Или все таки можно?

Чтобы переменная B существовала осмысленно, а также следуя из
диаграммы автомата мили
будем скажем прибавлять количество знаков к С если B>7, в ином случае будем вычитать;

Получим

$B = 0;
function a($var) {  
$C = 0;
for($i=0; $i<strlen($var); $i++) {  $B++;  if($B>7) {C++; }else  {C--; }}

return C;
}


Во втором случае получим уже С с аргументом БЫК равное -1;
На практике не проверял, но думаю, что должно работать. Хотя к пинокоду это отношения не имеет, но для меня на данный момент важно понять насколько я усвоил понятие конечного автомата.
Все ли я правильно понял? Есть ли еще какие-то факторы отличающие конечный автомат?
Очень хотелось бы услышать ответ независимо от того, прав я или нет.
28.12.2012, 02:05
Ответить
NO USERPIC

rgbeast

В целом правильно. Думаю, суть автомата станет яснее, если передавать ему не строку, а один символ. В этом случае в самом автомате цикла не будет (цикл будет на входе автомата) и польза от изменения и сохранения состояния будет понятней.
28.12.2012, 10:03
Ответить
NO USERPIC

platedz

Большое спасибо за ответ, только вот с циклом на входе я как-то не очень понял.
28.12.2012, 14:16
Ответить
NO USERPIC

platedz

$B = 0;
for($i=0; $i<strlen($var); $i++) {
function a($i)
{

$B++;

return $B;
}

}
Это имелось ввиду?
28.12.2012, 16:36
Ответить
NO USERPIC

rgbeast

Имеется в виду, что сам автомат обрабатывает только один символ. Поэтому функцию кто-то должен вызывать посимвольно. Вызов автомата будет выглядеть примерно так:
for($i=0; $i<strlen($var); $i++) {
 a($var[$i]);
}


Тут подчеркивается, что строка обрабатывается последовательно и при обработке каждого символа конечный автомат меняет свое внутреннее состояние. Если тема интересна, почитайте также про машину Тьюринга.
29.12.2012, 01:55
Ответить
NO USERPIC

platedz

Большое спасибо. Тема действительно заинтересовала. Обязательно почитаю.
29.12.2012, 03:21
Ответить
NO USERPIC

platedz

Подскажите, пожалуйста, а чем конечный автомат отличается от рекурсии? Где-то читал, что они отличаются, но единственным отличием, которое приходит в голову, что не всякий автомат является рекурсией, но при этом любая рекурсия является автоматом. Или я ошибаюсь?
29.12.2012, 08:52
Ответить
NO USERPIC

rgbeast

Конечный автомат - это готовый алгоритм, а рекурсия - один из методов, который может быть частью алгоритма. Тюринг показал, что машина Тюринга (обобщение конечного автомата) может решить любую алгоритмизируемую задачу. Это означает, что без рекурсии можно всегда обойтись.
30.12.2012, 15:46
Ответить
NO USERPIC

platedz

В общем и целом более или менее разобрался, по крайней мере с кодированием, но осталось несколько вопросов.
Разбирал функцию _encode в php
http://xn----9sbcmrygis2b.xn--p1ai/rfc/3492.html
Весь алгоритм находится в функции _encode.
Неясными остались следующие параметры. Что они делают и зачем?
Так например понятно, что _tmax - это количество букв латинского алфавита
а _base - это количество букв латинского алфавита и цифры.
а initial_n - это количество ascii символов
А вот следующие параметры абсолютно непонятны.
skew = 38
damp = 700
initial_bias = 72
Поясните, пожалуйста, что они значат и для чего служат?
Также в функции _encode_digit неясны, что это за 22, 75 и 26
01.01.2013, 02:41
Ответить
NO USERPIC

rgbeast

Честно говоря, не знаю их значение. Это некоторые константы, зафиксированные стандартом. Они входят в вычисления и от них видимо зависит как будут закодированы определенные символы. Надо экспериментировать с алгоритмом при разных значениях параметров.
01.01.2013, 15:49
Ответить
NO USERPIC

platedz

Спасибо за ответ.
В функции _encode_digit я так понял 26 это количество символов латинского алфавита.
initial_bias - это 72, вполне подходит 36*2, а 36 это количество символов и цифр. Хотя с другой стороны почему бы не 108.
skew = 38 - а 38 - это количество символов цифр и знак - и _
А с encode_digit и вовсе неясно, кроме возможно числа 26, которое равно количеству латинских букв.
damp мне вообще показался произвольным числом, так сказать от балды взятым. Хотя не исключаю, что и большая часть остальных цифр, также не имеют особой логики и служат скажем для того, чтобы создать какой-то стандарт и порядок.
01.01.2013, 17:25
Ответить
NO USERPIC

platedz

Читаю про вес цифр, правда пользуясь переводчиком
http://en.wikipedia.org/wiki/Numeral_system#Generalized_variable-length_integers

1) 304 = 3×100 + 0×10 + 4×1 или более точно 3×102 + 0×101 + 4×100
Здесь насколько я понимаю, это вес 10,

а здесь
7 + 3*8 + 4*64 = 287
вес 8

Хотя следуя этому выражению
Цитата:
Например, в основе 8 целых чисел 437, цифры 7, 3, и 4, и веса 1, 8, и 64, таким образом, значение 7 + 3*8 + 4*64 = 287.


То получается, что вес это 8(или 10) в степени порядкового номера числа справа налево, начиная с нуля.

Как вообще это правильно будет? И как правильно понимать слово вес, в таких случаях в тех же документациях/инструкциях?
04.01.2013, 18:23
Ответить
NO USERPIC

platedz

А еще не ясно что значит mod в t + ((N - t) mod (base - t)),
и div в N (N - t) div (base - t)
04.01.2013, 18:28
Ответить
NO USERPIC

rgbeast

div - целая часть при делении, mod - остаток от деления
04.01.2013, 20:18
Ответить
NO USERPIC

platedz

Большое спасибо за ответ. Напишите, пожалуйста, какое-нибудь простое уравнение отражающее это.
И по поводу веса тоже как-то не очень понятно.
04.01.2013, 21:18
Ответить
NO USERPIC

rgbeast

http://ru.wikipedia.org/wiki/%C4%E5%EB%E5%ED%E8%E5_%F1_%EE%F1%F2%E0%F2%EA%EE%EC
05.01.2013, 02:18
Ответить
NO USERPIC

platedz

Спасибо, огромное. С весом бы еще разобраться и будет совсем отлично.
05.01.2013, 02:26
Ответить
NO USERPIC

rgbeast

Ну это объяснение про восьмеричную систему. Здесь 437(восьмеричное) = 4*64 + 3*8 + 7 = 287. Подробно про системы счисления здесь: http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F
06.01.2013, 01:03
Ответить
NO USERPIC

platedz

Поясните, пожалуйста, что такое кодировка ascii2
http://commons.wikimedia.org/wiki/File:Ascii2.gif?uselang=ru
Т.е. ascii
http://commons.wikimedia.org/wiki/File:Ascii1.gif?uselang=ru
вроде понятно, она вроде как используется везде, т.е. во всех кодировках, до 128 символа
а вот с ascii2, как то я не понял.
05.01.2013, 20:12
Ответить
NO USERPIC

rgbeast

Эта картинка относится к статье про кодировку CP1251 ( http://ru.wikipedia.org/wiki/Windows-1251?uselang=ru ). В этой кодировке таким способом заполнена вторая половина таблицы.
06.01.2013, 01:08
Ответить
NO USERPIC

platedz

Спасибо большое за ответ. Т.е. если я правильно понял, эта картинка относится только к cp1251.
Если да, то буду признателен если еще про вес цифр объясните.
06.01.2013, 01:48
Ответить
NO USERPIC

rgbeast

По всей видимости так. Про вес - см. ссылку на системы счисления в ответе выше.
06.01.2013, 02:01
Ответить
NO USERPIC

platedz

Спасибо большое, не заметил.
06.01.2013, 02:57
Ответить
NO USERPIC

platedz

Спасибо за ссылку. С кодировками у меня вроде вопросов нет, а вот с весом как-то я не очень уверен.
http://en.wikipedia.org/wiki/Numeral_system#Positional_systems_in_detail
В частности исходя из таблицы насколько я понимаю
Скажем в двоичной системе исчисления вес - это 2 в степени n
как в таблице b в степени n.
А в шестнадцатиричной это 16 в степени n.
Правильно ли я понимаю.
И еще вопрос про digit, где у "a" тройка в нижнем регистре.
Т.е. тройка в верхнем регистре, это обозначение степени, а вот в нижнем?
07.01.2013, 00:57
Ответить
NO USERPIC

rgbeast

Индекс в нижнем регистре - номер цифры в числе от младшей к старшей. То есть для числа 792, a0=2, a1=9, a2=7
08.01.2013, 17:58
Ответить
NO USERPIC

platedz

Спасибо за ответы.
08.01.2013, 18:54
Ответить
Добавить комментарий
Отображение комментариев: Древовидное | Плоское
© 2008—2024 webew.ru, связаться: x собака webew.ru
Сайт использует Flede и соответствует стандартам WAI-WCAG 1.0 на уровне A.
Rambler's Top100

Реклама: