В споре рождается истина

- А я так не думаю!

Архив Август 2010

Избитая тема про музыку вконтакте

с 2 комментариями

Вообще уже настало время, когда хранить музыку на винчестере смысла особого нет.
Но, блин, с инетом проблемы бывают. Поэтому пусть пока лучше будет :)

Итак, как сохранить свою музыку с сайта вконтакте на свой компьютер?

Если посмотреть код страницы “Аудиозаписи”, то можно заметить, что код разбит на div’ы, span’ы и тд, что позволяет легко вычленить ссылки на mp3-шки и получить сведения о песне (название, группа). И сохранить с нормальными названиями, а не просто комбинациями цифр и букв.

Кажется, что все просто, но это не так.
У меня 173 аудиозаписи, это все разбито на 2 страницы (100 штук на первой, остальное на второй).
Когда я перехожу на вторую страницу – в исходнике ничего не меняется. Ничего страшного, конечно, но просто остаются те же 100 песен, что были на 1-й странице.

Хаха, не трудно догадаться, что здесь замешан так горячо любимый мною JavaScript.
В Opera можно легко отключить javascript, после чего переход на вторую страницу позволяет просмотреть ее исходный код и увидеть оставшиеся 73 песни.

Структура кода примерно такая:

...
<div class="audioRow" id="audio84309192">
<a name='84309192'></a>
 <table width="100%"><tbody>
 <tr><td style="width: 20px; vertical-align:top">
 <img class="playimg" onclick="return operate(84309192,'http://cs4707.vkontakte.ru/u12848345/audio/e7bffd8f5682.mp3',281);" id="imgbutton84309192" nosorthandle="true" src="images/play.gif"/>
 </td>
 <td style="width: 360px;"><div class="audioTitle">
  <b id="performer84309192"><a href='gsearch.php?section=audio&c[q]=Queen'>Queen</a></b><span>&nbsp;-&nbsp;</span><span id="title84309192"><a href='javascript: showLyrics(84309192,4589379);'>I Want It All</a></span> </div>
  <div class="duration">4:41</div>
 </td>
 </tr>
 </tbody></table>

<div style="height:14px;margin-left:28px;">
<div id="line84309192" class="playline"></div>
<div id="toddler84309192" class="toddler">
</div>
<div id="player84309192" style="display: none;" class="playerClass">
</div>
</div>

<div id="lyrics84309192"></div>
</div>

<div class="audioRow" id="audio81408147">
<a name='81408147'></a>
 <table width="100%"><tbody>
 <tr><td style="width: 20px; vertical-align:top">
 <img class="playimg" onclick="return operate(81408147,'http://cs4718.vkontakte.ru/u59481183/audio/c3ff1145f6ec.mp3',146);" id="imgbutton81408147" nosorthandle="true" src="images/play.gif"/>
 </td>
 <td style="width: 360px;"><div class="audioTitle">
  <b id="performer81408147"><a href='gsearch.php?section=audio&c[q]=Валерий Горбачев'>Валерий Горбачев</a></b><span>&nbsp;-&nbsp;</span><span id="title81408147">До первого убитого</span> </div>
  <div class="duration">2:26</div>
 </td>
 </tr>
 </tbody></table>

<div style="height:14px;margin-left:28px;">
<div id="line81408147" class="playline"></div>
<div id="toddler81408147" class="toddler">
</div>
<div id="player81408147" style="display: none;" class="playerClass">
</div>
</div>

<div id="lyrics81408147"></div>
</div>
...

Отличие между этими двумя песнями в том, что для первой есть слова, а для второй – нет.
Таким образом, в Song! может внутрь вставляться гиперссылка и тогда получается 

Song!

.

Уже зная это можно написать программу на любом тьюринг-полном.
Я написал скрипт на Ruby. Работать с ним надо так:

  1. Поместить его в папку, куда должны скачиваться файлы
  2. Сохранить в эту папку файлы страниц вконтакте с ссылками на аудиофайлы
  3. Запустить скрипт, ввести имена данных файлов
  4. Подождать

Вот, что было у меня:

Можно заметить, что есть несколько песен, скачанных с ошибкой:

причем первая песня была недоступна с сервера (не проигрывалась даже на самом контакте), а вторая судя по всему содержала запрещенный символ в названии.
Думаю, результат можно считать удовлетворительным.

Вот мой скрипт:

#script helps you to download music
#author jtim, 17 august, 2010
#email jtimchenko@gmail.com
require 'rubygems'
require 'hpricot'
require 'iconv'
require 'open-uri'

def download_file(link, filename)
  begin
    writeOut = open(filename, 'wb')
    writeOut.write(open(link).read)
    writeOut.close
  rescue
    return false
  end
  true
end

utf8 = Iconv.new("utf8", "windows-1251")
links = Hash.new

re_link = Regexp.compile("'(.*)'")
re_song = Regexp.compile("<.*?>")

loop{
  puts"Enter name of file to scan or empty line to start downloading..."
  input_file_name = gets.chomp
  break if input_file_name == ""

  begin
    (Hpricot(open(input_file_name))/'div.audioRow').each do |nd|
    begin
      fn = re_link.match((nd/'img')[0]['onclick'])[1]
      artist = utf8.iconv((nd/'a')[1].inner_html())
      song   = utf8.iconv((nd/'span')[1].inner_html()).gsub(re_song,'')
      links[fn] = artist + " - " + song+'.mp3'
    rescue
      puts "Error!"
      puts nd.to_html
      puts "-----"
    end
  end
  rescue
    puts "Error while opening file!"
  end

  links.each_key{|k|
    puts k+" : "+links[k]
  }

  puts "There are #{links.length} files in list!"  
}

all = links.length
num = 1
links.each_key{|k|
  print("downloading [#{links[k]}]: #{num} / #{all} : ")
  msg=''
  if download_file(k, links[k])
    msg='OK'
  else
    msg='ERROR!'
  end
  puts(msg)
  num+=1
}

Что надо отметить:

  1. Это работает для ruby 1.8. На ruby 1.9 я не проверял
  2. Используется gem hpricote для парсинга html файла – код библиотеки написан самим Why (автор книги why’s poignant ruby guide)
  3. Я заюзал регулярки, нифигасе!

Основные минусы:

  • Появляются символы типа “Vicky Leandros – Tango d'Amor.mp3″. Конечно же там должен стоять апостроф. Видимо, это возникает при переводе cp1251 в utf8.
  • Каждый файл скачивается за раз. Пока он не скачался полностью – ничего не сохранено. Как только файл скачается целиком – он сразу же будет записан на винт. Короче, если интернет часто обрывается, то скрипт становится почти бесполезным.

Основные плюсы:

  • Простота в использовании
  • Человеческие имена файлов
  • Теперь можно будет слушать музыку, не заходя на контакт!

p.s.: в посте есть парочка несмертельных ошибок, но исправлять сейчас уже нет сил. Надо бы поспать)

Написано jtimv

17.08.2010 в 08:18

Опубликовано в Программирование

Отмечено как

Processing

с 2 комментариями

Processing – это язык программирования для быстрого создания демонстраций. Ну или что-то типа того.

Он основан на java и может использовать все, что написано на java.
Созданные приложения можно экспортировать в веб-страничку с java-апплетом. Тогда код на Processing переводится на java.

После неудачной попытки сделать что-то красивое и полезное на javascript я решил попробовать processing.

Кончилось это тем, что я сделал небольшой sketch (зарисовка, в processing так называются проекты).
Он посвящен вставке элементов в бинарное дерево поиска.

А вот и видео: Binary search tree insertion demo

Все это заняло около 170 строк кода. По-моему, вполне лаконично.

UPD. Теперь я хочу сделать еще какую-нибудь визуализацию. Например, red-black-tree, AVL-tree. А может быть еще какую-нибудь структуру данных (типа дерева Фенвика, дерева отрезков или системы непересекающихся множеств).. Или даже алгоритм сортировки какой-нибудь.

Меня очень впечатлило это видео со сравнением QuickSort и BubbleSort и мини-соревнованием в конце :) : video

Написано jtimv

16.08.2010 в 03:19

Опубликовано в Программирование

Про поиск

с одним комментарием

Привет.
Что надо делать, если в данном тексте T (text) надо найти строку P (pattern) ?
Варианты:

  • Тупой поиск в лоб
  • Чуть-чуть более умный поиск (алгоритм Рабина-Карпа), где-то в челюсть
  • Поиск на основе конечных автоматов (пусть будет в пупок).
  • Модифицированный поиск на основе КА: Алгоритм Кнута-Морриса-Пратта. Да-да, как раз туда.
  • Есть еще много-много способов найти что-то в чем-то, например, алгоритм Ахо-Корасик и другие устрашающие комбинации фамилий

Если строка и текст довольно небольшие (пусть до 50 символов) – можно смело использовать первый вариант.
Но лучше даже в такой ситуации применить алгоритм Рабина-Карпа и быть спокойным.

Для более тяжелых случаев понадобится конечный автомат.
Чуть подробнее: мы строим для данного образца конечный автомат.
Состояния обозначаются номерами от 0 до m (длина образца). Если автомат находится в состоянии i, значит на данный момент совпало i символов образца и послендих i символов текста.
Понятное дело, перед поиском надо построить таблицу переходов.

Ну и в конце концов – само совершенство – алгоритм Кнута-Морриса-Пратта.
О нем все так много говорят! Иногда мне даже кажется, что я единственный человек на Земле, который не понял его!

Конечно, я решил исправлять ситуацию. Но, черт возьми, никак не могу врубиться, откуда свалилась эта префикс-функция? Как авторы вдруг догадались ее использовать?

Если вы оказываетесь в подобной ситуации, лучшим выходом будет просто открыть Кормэна, найти, прочитать и понять нужную главу, а потом выполнить упражнения. Если вы не смогли выполнить эти упражнения – значит вы не нашли нужную главу, или не прочитали ее. Ну или не поняли. Но как правило понимание приходит во время решения упражнений.

Есть небольшая деталь. Очень эффективно применять КА или КМП, если есть один шаблон и много текстов. Фактически один раз мы строим таблицу переходов, а потом просто просматриваем тексты за 1 проход и знаем количество вхождений и их “координаты”.

Интереснее другое. Что, если образцов много, а текст – один?
Ну, например, решили выяснить – кто же все-таки отец (из этих 30) данного человека? Я правда не знаю, может там и не поиск подстроки…

Все эта каша-малаша возникла у меня в голове, когда я пытался решить эту задачу:

http://codeforces.com/contest/25/problem/E

А потом я решил сделать еще кое-что.
Вот скриншот (не знаю, где есть нормальный хостинг, чтобы выложить это):

Конечный автомат для поиска образца в тексте

Сделал я это на JavaScript. Для вывода графов использовал какой-то глючный минифреймворк dracula, на который даже ссылку давать не хочу.

Я еще давно понял, что мы с JavaScript созданы не друг для друга. Так что спешу перечислить основные минусы JavaScript:

  • Это не Ruby и даже не C++
  • Какие-то странные приколы с переменными.
    var a = 3;
b = 2;
delete b; // можно, удаляется созданное нами же свойство объекта window
delete a; // нельзя, пытаемся удалить переменную
  • Пусть есть строка a. Не знаю, почему, но у меня a[i] не ратало. Пришлось делать a.charAt(i)
  • Непонятная ситуация с массивами. Например, такой код у меня не работал так, как я ожидал:
    var a = [1,2,3];
for (i in a)
    alert(i);

    Надо делать так:
    var a = [1,2,3];
for (i in a)
    alert(a[i]);

    По-моему, довольно странно. Я же не объявлял массив как ассоциативный массив !

К этому надо прибавить невозможность нормальной отладки и разные реакции браузеров на один и тот же код. И да, эта конченая библиотека для рисования графов. Она не позволяет изменять или перерисовывать графы. Формируй граф до загрузки страницы – и никак иначе!

Резюме.
javascript – это совершенно отличный от C++ язык, взять хотя бы прототипы и замыкания.

Поиск подстроки в строке – интересная задача, имеющая не менее интересные алгоритмы решения, в том числе Рабина-Карпа, Ахо-Корасик, конечный автомат, КМП и так далее.

Написано jtimv

11.08.2010 в 19:59

Опубликовано в Программирование

Follow

Get every new post delivered to your Inbox.