Namazu-devel-ja(旧)
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: About PageRank(TM) (Re: improvements of scoring method)
From: Rei FURUKAWA <furukawa@xxxxxxxxxxxx>
Subject: [namazu-devel-ja] Re: About PageRank(TM) (Re: improvements of scoring method)
Date: Sat, 17 Feb 2001 02:22:02 +0900
> baba> そもそも、public な論文に載っている初歩的な数学ルーチンは、既に
> baba> 「公知の技術」ですよね。僕が参照したのはその原理だけで、あとは数学
> public な論文を出す前に特許を出願する場合もあるので、その点は
> 注意が必要だと思います。
はい、それはあるかなともおもって、出願日だけでも調べられるかな？と
いうことでhttp://www.ustpo.gov/ をあたったのですが、どうも出てきま
せん。じゃ、少なくとも Trademark 登録はされているだろうとおもった
のですが、これも出てきません。出願日からある程度経ったら公開公報と
して出てくるとおもったのですが... さすがにそんなに詳しくないし、根
本的に勘違いしている可能性大ですかね？
> baba> ＃ 後半部はともかく、前半部もそんなに難しかったでしょうか？
> # どこまでが「前半部」でしょうか？
あ、簡単な実例で説明している3章までのつもりでした。4章以降は、内容
的に多少高度ということもありますが、それよりは僕自身の中でわかった
つもりでもまだ十分にこなれていない部分もけっこうあるので、文章にも
飛躍や説明不足が多いということで...
> 見ました。とても面白いです。これを参考に、いろいろ式を変形し
> て遊んでいます。そこで、ちょっと質問なのですが、
> (1) emacs で、octave/matlab に適した major mode は、何か無いで
> しょうか？
Octave のソースコードの中に octave.el (といくつか附属の elisp 群)
があるようです。僕は Kondara の RPM をそのまま入れましたが、
/usr/doc/octave 以下に入っていました。
> > この隣接リストで表現されるリンク関係の隣接行列 A は
> この A から
> > PageRank 式の推移確率行列 M は、A を転置しそれぞれの列を
> > 非零要素数で割った、以下のような7×7の正方行列になる。
> この M を計算する、効率のよい方法は、なんでしょう？とりあえず、
> octave 初心者としては、
> A = A'
> M = ones(columns(A),1) * (1 ./ max(1,sum(A, 1))) .* A
> くらいしか思いつきませんでしたが…
僕も Octave はまったく初心者 :-) です。だって初めて作った octave
スクリプトだもの。だから、単純に for ループを回しました。(^_^;)
M = zeros(N,N)
for r=1:N
nlink = length(find(A(r,:)));
if (nlink != 0)
M(r,:) = A(r,:) ./ nlink;
endif
end
M = M'
とかですか。むー、美しくないですね。それに遅いとおもいますし。
ただ、いま動いているものは、web ページにも書いてますが、内部では隣
接リストの形で圧縮して保持するようにしています。そうしないと、Nが
大きいとメモリが足りなくなってしまうんで。だから M の作り方は上の
とは違ってもう少し複雑になってます。
> # 「仮想モデルと現実世界との相違」をどう計算に織り込むか、の
> # 部分が一番興味のあるところです。いろいろ実験してみます。
そうですよね。HITS とかでも A'A や AA' の固有ベクトルがハブやオー
ソリティ計算の基本になってるわけで(動的に計算するという点では
PageRank とは違いますが)、いろいろ応用も効きそうですし、遊びがいが
あるとおもいます。
んで、とりあえず道具立てとして、準備用のスクリプトだけ先にお送りし
ておきます。＃ すみません、なかなかドキュメントがそろわない... _o_
ひとつは lnnmz.pl です。岡野さんと古川さんがお作りになって既に
commitされていたものを、相対リンク対応などのためにざくざく手を入れ
たものです。といっても機能面ではほとんど変わらないのですが。違うの
は、先頭付近で
my %inv_replace = (
"http://www.apache.org" => "/home/httpd/html",
);
という設定を入れて、webコンテンツの中で http: 表示で書いてあっても
ローカルコンテンツは相対リンクとして扱うようにしました。意味的には
ちょうど Replace 機能の逆になります。ただ、この設定をうまく外に追
い出す方法がおもいつかなかったので、とりあえずベタに書いてます。あ
と、ぼくが正規表現だとおもっているものは実は正規表現ではないとおも
うので、直してくださるとありがたいです。
Usage: lnnmz.pl [indexdir]
入力: NMZ.r, HTML本体
出力: NMZ.field.link
NMZ.field.link は、DocID 発のリンクを文字列のまま保存したもの。
もうひとつは adnmz.pl で NMZ.field.link から NMZ.field.adjacency
を作ります。これは、文書間のリンク関係を文書IDに変換したもので、隣
接リストそのものです。手元では、NMZ.field.adjacency を呼んで
PageRank 計算をさせるようにしています。
Usage: adnmz.pl [indexdir]
入力: NMZ.r, NMZ.field.link
出力: NMZ.field.adjacency
いずれも良いようなら、commit したいとおもっています。
--
馬場 肇 ( Hajime BABA ) E-mail: baba@xxxxxxxxxxxxxxxxxxxxxx
京都大学理学部宇宙物理学教室 博士後期課程
--#! /usr/bin/perl -w
# -*- Perl -*-
# lnnmz - program to make NMZ.field.link
# $Id$
#
# Copyright (C) 2000 osamu2001@xxxxxxxxxxxx All rights reserved.
# Copyright (C) 2000 furukawa@xxxxxxxxxxxx All rights reserved.
# Copyright (C) 2001 Hajime BABA All rights reserved.
# Copyright (C) 2001 Namazu Project All rights reserved.
# This is free software with ABSOLUTELY NO WARRANTY.
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either versions 2, or (at your option)
# any later version.
#
# This program is distributed in the hope that it will be useful
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
# 02111-1307, USA
#
# This file must be encoded in EUC-JP encoding
#
package lnnmz;
{
my($tmp) = $0;
$tmp = "./$tmp" if $tmp !~ /[\/\\]/;
while ($tmp =~ /^(.*[\/\\])/){
unshift(@INC, $1);
last if !-l $tmp;
$tmp = $1 . $tmp if ($tmp = readlink($tmp)) !~ /^\//;
}
}
use strict;
use Cwd;
use File::Spec;
#push(@INC, '@PERLLIBDIR@');
require 'nmzidx.pl';
# for example
my %inv_replace = (
"http://www.apache.org"; => "/home/httpd/html",
);
my $backup;
while (@ARGV && $ARGV[0] =~ s/^\-//){
my $argv = shift;
&usage, exit if $argv eq '-help';
$backup = 0, next if $argv eq '-no-backup';
while ($argv =~ s/^(.)//){
$backup = 0 if $1 eq 'b';
}
}
if (@ARGV){
for my $argv (@ARGV){
$argv =~ s/NMZ$// unless -d $argv;
$argv = '.' if $argv eq '';
&lnnmz($argv, $backup) if -d $argv;
}
} else {
&lnnmz('.', $backup);
}
exit(0);
# main routine
sub lnnmz{
my ($dir, $backup) = @_;
my $nmzi = new nmzidx($dir, 'r');
my $fh = $nmzi->open_flist;
my $nmzo = new nmzidx($dir, 'w');
my $fo = $nmzo->open_field('link');
my %list_f;
while (defined $fh->read(\%list_f)){
my $fname = $list_f{'r'};
# print "@@ $fname\n";
open(F, $fname) || die;
my @href = get_href($fname, <F>);
close(F);
my $tmp = join(" ", @href);
$fo->{'link'}->putline("$tmp\n");
# print "@@ $tmp\n";
}
$nmzo->replace_db($backup);
$nmzi->close;
}
# mmm... tooooooooo dirty, but it seems to work good. X-(
# Pls clean up the code!
sub get_href {
my ($fname, @lines) = @_;
my ($basedir, $file) = splitpath($fname);
my (@href, %count);
foreach my $line (@lines) {
if ($line =~ /<a\s[^>]*href=([\"\'])(.*?)\1/ig) { #"
my $href = $2;
next if ($href =~ /^(ftp|mailto):/); # only http: or file:
if (($href !~ m:^/:) && ($href !~ m/^http:/)) {
$href = rel2abs($href, $basedir);
$href = canonpath($href) ;
}
$href =~ s/#.*$//g;
$href =~ s:([^/]*)/\.\.::g;
foreach my $url (sort keys %inv_replace) {
my $dir = $inv_replace{$url};
$href =~ s:^$url:$dir:g;
$href =~ s:^/$:$dir/index.html:g;
}
$href =~ s:/$:/index.html:g;
$href =~ s:/\.$:/index.html:g;
if ($href !~ m/^http:/) {
$href = canonpath($href) ;
}
push(@href, $href) unless $count{$href};
$count{$href}++;
}
}
{
# uniq and sort
my %count;
@href = grep(!$count{$_}++, @href);
@href = sort {$count{$a} <=> $count{$b}} @href;
}
return @href;
}
# Splits a path into directory and filename portions.
sub splitpath($) {
my ($path) = @_;
my ($dir, $file) = ('', '');
$path =~ m|^ ( (?: .* / (?: \.\.?\z )? )? ) ([^/]*) |xs;
$dir = $1;
$file = $2;
# print "dir=$dir, file=$file\n";
return ($dir, $file);
}
# Converts a relative path to an absolute path.
sub rel2abs($$) {
my ($path,$base ) = @_;
# Clean up $path
if ( ! File::Spec->file_name_is_absolute( $path ) ) {
# Figure out the effective $base and clean it up.
if ( !defined( $base ) || $base eq '' ) {
$base = cwd() ;
}
elsif ( ! File::Spec->file_name_is_absolute( $base ) ) {
$base = rel2abs( $base ) ;
}
else {
$base = canonpath( $base ) ;
}
# Glom them together
$path = File::Spec->catdir( $base, $path ) ;
}
return canonpath( $path ) ;
}
sub canonpath {
my ($path) = @_;
$path =~ s|/+|/|g unless($^O eq 'cygwin'); # xx////xx -> xx/xx
$path =~ s|(/\.)+/|/|g; # xx/././xx -> xx/xx
$path =~ s|^(\./)+||s unless $path eq "./"; # ./xx -> xx
$path =~ s|^/(\.\./)+|/|s; # /../../xx -> xx
$path =~ s|/\z|| unless $path eq "/"; # xx/ -> xx
return $path;
}
sub usage{
print
("Usage: lnnmz [options] <target(s)>\n" .
" --help show this help and exit.\n" .
" -b, --no-backup do not backup original file.\n"
);
}
# EOF
#!/usr/bin/perl
# -*- Perl -*-
# adnmz.pl - make NMZ.field.adjacency
# $Id$
#
# Copyright (C) 2001 Hajime BABA All rights reserved.
# Copyright (C) 2001 Namazu Project All rights reserved.
# This is free software with ABSOLUTELY NO WARRANTY.
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either versions 2, or (at your option)
# any later version.
#
# This program is distributed in the hope that it will be useful
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; if not, write to the Free Software
# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
# 02111-1307, USA
#
# This file must be encoded in EUC-JP encoding
#
package adnmz;
{
my($tmp) = $0;
$tmp = "./$tmp" if $tmp !~ /[\/\\]/;
while ($tmp =~ /^(.*[\/\\])/){
unshift(@INC, $1);
last if !-l $tmp;
$tmp = $1 . $tmp if ($tmp = readlink($tmp)) !~ /^\//;
}
}
use strict;
use Cwd;
use File::Spec;
#push(@INC, '@PERLLIBDIR@');
require 'nmzidx.pl';
my $backup;
while (@ARGV && $ARGV[0] =~ s/^\-//){
my $argv = shift;
&usage, exit if $argv eq '-help';
$backup = 0, next if $argv eq '-no-backup';
while ($argv =~ s/^(.)//){
$backup = 0 if $1 eq 'b';
}
}
if (@ARGV){
for my $argv (@ARGV){
$argv =~ s/NMZ$// unless -d $argv;
$argv = '.' if $argv eq '';
&adnmz($argv, $backup) if -d $argv;
}
}else{
&adnmz('.', $backup);
}
exit(0);
# read NMZ.field.link, and make NMZ.field.adjacency
sub adnmz {
my ($dir, $backup) = @_;
# pretreatment: read NMZ.r, then make %docid and $ndoc.
my (%docid, $ndoc);
my $nmzr = new nmzidx($dir, 'r');
my $fr = $nmzr->open_flist;
my %list_f;
while (defined $fr->read(\%list_f)){
my $file_name = $list_f{'r'};
$docid{$file_name} = $ndoc + 1; # NOTE: DocID begins with 1.
$ndoc++;
}
$nmzr->close;
# Body: read NMZ.field.link, pick up of destination IDs using %docid,
# then write IDs list to NMZ.field.adjacency.
my $nmzi = new nmzidx($dir, 'r');
my $fi = $nmzi->open_field('link');
my $nmzo = new nmzidx($dir, 'w');
my $fo = $nmzo->open_field('adjacency');
while (defined (my $line = $fi->{'link'}->getline())){
chop($line); # important !!!
# print "@@ $line\n";
my @destid; # destination IDs from page_i to page_j
my @href = split(/ /, $line);
foreach my $h (@href) {
next if ($h =~ /^http:/); # consider with internal link only
if (defined $docid{$h}) {
push(@destid, $docid{$h});
next;
}
}
{
# uniq and numerical sort
my %count;
@destid = grep(!$count{$_}++, @destid);
@destid = sort {$a <=> $b} @destid;
}
my $links = join(" ", @destid);
$fo->{'adjacency'}->putline("$links\n");
}
$nmzo->replace_db($backup);
$nmzi->close;
}
sub usage{
print
("Usage: adnmz [options] <target(s)>\n" .
" --help show this help and exit.\n" .
" -b, --no-backup do not backup original file.\n"
);
}
# EOF