第 7 回アルゴリズムイントロダクション輪講会資料2008年12月04日 23時08分

すでにニュースでも伝えられている通り、12 月 1 日に第 7 回アルゴリズムイントロダクション輪講会がありました。今回の担当は私だったので、その発表資料を公開します。

  1. 中央値と順序統計量 (その 1)
    1. 予定
    2. 順序統計量とは
    3. 選択問題とは
    4. 最小値と最大値
    5. 平均線形時間選択アルゴリズム
  2. 中央値と順序統計量 (その 2)
    1. 最悪線形時間選択アルゴリズム
    2. 3 つずつのグループに分割した場合
    3. 7 つずつのグループに分割した場合
    4. 参考文献
  3. 中央値と順序統計量 (補足)
    1. 4 つずつのグループに分割した場合
    2. 6 つずつのグループに分割した場合
    3. Lazy-Select
    4. Randomized-Partition
    5. スタッフロール

「どうせ後から Web で公開するんだから、PDF とか見るのに手間がかかるものは使ってられないよね。やっぱ時代は XML 複合文書でしょ!」と、数式を表現するのに MathML を使いまくったら、なぜか Firefox 以外ではまともに表示されなくなってしまいました。ホスト言語が XHTML なので、IE にいたっては地の文の表示すらできません。

とは言っても MathML の仕様書を斜め読みしただけなので、適切でないマークアップが結構含まれています。本当は図も SVG で表現したかったのですが、いろいろと余裕がなかったのであきらめました。資料が 3 つ (本番では補足を除く 2 つ) の文書に分かれているのは、Firefox で MathML の要素数が一定数を越えると、文字揃えが効かなくなるというバグに遭遇したためです。

なお、MathML の記述に当たっては以下を参考にしました。

ちなみに私は今のところ風邪の症状は出ていないようです。

HTML と XHTML で同じ XPath を使う2008年12月11日 22時43分

通常、XPath を書くときは //p のようにすることが多いと思いますが、これには名前空間の指定が含まれていないため、XHTML 文書 (MIME タイプが application/xhtml+xml で提供されている文書) では使えません。これに対するアプローチとしては、//h:p のようにあらかじめ XPath 式に名前空間の指定を含めておき、リゾルバによる名前空間接頭辞の解決時に HTML と XHTML とで処理を分けるというのが一般的でした。「XPathNSResolver のクロスブラウザとか」や「document.contentType == "application/xhtml+xml"なページでの$X」で扱っている方法です。

とはいえ、いちいち名前空間接頭辞を指定するのは面倒くさいですし、同じ名前空間に対する接頭辞が人によって違うのも不便です。XPath 式の中で要素名と思われる部分は限定されるのだから、正規表現による置換で接頭辞を追加できないかと考えていました。しかし、ここでネックになるのが演算子です。XPath の演算子には英字からなるものがあり、たとえば式 div div div div div において、1、3、5 番目の div は div 要素に対する名前テストですが、2、4 番目の div は除算演算子となります。このような場合に、要素名に相当する箇所にだけマッチする正規表現を作るのは非常に難しいことです。

そこで、正規表現で要素名のみを抜き出すのをあきらめ、XPath 式を構成するすべてのトークンを順に見ていき、直前のトークンの情報を参考にして現在のトークンが要素名か否かを判断することにしました。この方法で XPath 式中の要素名に名前空間接頭辞を追加するコードは以下のようになります。

function addDefaultPrefix(xpath, prefix) {
  const tokenPattern = /([A-Za-z_\u00c0-\ufffd][\w\-.\u00b7-\ufffd]*|\*)\s*(::?|\()?|(".*?"|'.*?'|\d+(?:\.\d*)?|\.(?:\.|\d+)?|[\)\]])|(\/\/?|!=|[<>]=?|[\(\[|,=+-])|([@$])/g;
  const TERM = 1, OPERATOR = 2, MODIFIER = 3;
  var tokenType = OPERATOR;
  prefix += ':';
  function replacer(token, identifier, suffix, term, operator, modifier) {
    if (suffix) {
      tokenType = (suffix == ':' || (suffix == '::' &&
                   (identifier == 'attribute' || identifier == 'namespace')))
                  ? MODIFIER : OPERATOR;
    } else if (identifier) {
      if (tokenType == OPERATOR && identifier != '*')
        token = prefix + token;
      tokenType = (tokenType == TERM) ? OPERATOR : TERM;
    } else {
      tokenType = term ? TERM : operator ? OPERATOR : MODIFIER;
    }
    return token;
  }
  return xpath.replace(tokenPattern, replacer);
}
addDefaultPrefix("div div div div div", "h");
// => "h:div div h:div div h:div"

addDefaultPrefix("//div[not(@id)][p]", "h");
// => "//h:div[not(@id)][h:p]"

この中で、トークンを切り出すための正規表現を、Perl 正規表現の x オプションをイメージして整形すると次のようになります。XML 1.0 第 5 版で名前として使える文字列はすべて識別子として受け入れられるようにしました。

/ # identifier
  ( [A-Za-z_\u00c0-\ufffd] [\w\-.\u00b7-\ufffd]* | \* )
      # suffix
  \s* ( ::? | \( )?
  # term
| ( ".*?" | '.*?' | \d+ (?: \.\d* )? | \. (?: \. | \d+ )? | [\)\]] )
  # operator
| ( \/\/? | != | [<>]=? | [\(\[|,=+-] )
  # modifier
| ( [@$] ) /g

この関数を実際に使用するには文書が XHTML であることを判別しなければなりません。ここでは、もう少し一般的に考え、XPath 式を評価する際のコンテキストノードがデフォルト名前空間を持っていれば、XPath 式中の接頭辞を持たない要素名はそのデフォルト名前空間に属するものとして扱うことにします。デフォルト名前空間は lookupNamespaceURI メソッドの引数に null または空文字列を渡せば取得できますが、Safari では null を、Opera では空文字列を渡さないとうまく動かないので、引数が null の場合と空文字列の場合を併記しています。

function $X(xpath, context) {
  context = context || document;
  var expr   = createXPathExpression(xpath, context);
  var result = expr.evaluate(context, XPathResult.ANY_TYPE, null);
  switch (result.resultType) {
  case XPathResult.NUMBER_TYPE:  return result.numberValue;
  case XPathResult.STRING_TYPE:  return result.stringValue;
  case XPathResult.BOOLEAN_TYPE: return result.booleanValue;
  default:
    result = expr.evaluate(context, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
    var nodes  = [];
    var length = result.snapshotLength;
    for (var i = 0; i < length; i++)
      nodes.push(result.snapshotItem(i));
    return nodes;
  }
}

function createXPathExpression(xpath, context) {
  context = context || document;
  var doc       = context.ownerDocument || context;
  var resolver  = doc.createNSResolver(context.documentElement || context);
  var defaultNS = context.lookupNamespaceURI(null) ||
                  context.lookupNamespaceURI("");
  if (defaultNS) {
    const defaultPrefix = "__default__";
    xpath = addDefaultPrefix(xpath, defaultPrefix);
    var defaultResolver = resolver;
    resolver = function (prefix) {
      return (prefix == defaultPrefix)
             ? defaultNS : defaultResolver.lookupNamespaceURI(prefix);
    };
  }
  return doc.createExpression(xpath, resolver);
}

以下がサンプルです。文書が text/html、application/xhtml+xml、text/xml のいずれの MIME タイプで提供されていても、同じ XPath 式を使えることが確認できるでしょう。

これを使えば、XPath を使うアプリケーションを XHTML へ対応させるのが簡単になるかと思います。実際に、AutoPagerize を XHTML に対応させるパッチを書いてみました。これには、XHTML への対応に加え、現在のページと 2 ページ目以降で URI の階層が異なるとき、相対 URI の解決に失敗する問題の修正も含まれています。このパッチを AutoPagerize に適用した上で、次の SITEINFO を追加すれば、MIME タイプ application/xhtml+xml で提供されている「水無月ばけらのえび日記」でも AutoPagerize が動作します。

    {
        url:          'http://bakera\\.jp/ebi(?:[/?#]|$)',
        nextLink:     '//link[@rel="prev"]',
        pageElement:  'id("main-contents")',
        exampleUrl:   'http://bakera.jp/ebi',
    },