1-2hit |
Kazuya WAKATA Hiroaki SAITO Kunihiro FUJIYOSHI Keishi SAKANUSHI Takayuki OBATA Chikaaki KODAMA
In this paper, for convex rectilinear block packing problem, we propose 1) a novel algorithm to obtain a packing based on a given sequence-pair in O(n2) time (conventional method needs O(n3) time), where n is the number of rectangle sub-blocks made from convex blocks, 2) a move operation for Simulated Annealing which is symmetric and can guarantee reachability for the first time, and 3) a method to generate a random adjacent sequence-pair in O(n2) time. By using 1), 2) and 3) together, the time complexity of the inner loop in Simulated Annealing becomes surely O(n2) time. Experimental results show that the proposed algorithm is faster than the conventional ones in practical and the wire length as well as packing area is taken into consideration in the proposed method.
Tomohisa SANO Shiho Hoshi NOBESAWA Hiroyuki OKAMOTO Hiroya SUSUKI Masaki MATSUBARA Hiroaki SAITO
Toponyms and other named entities are main issues in unknown word processing problem. Our purpose is to salvage unknown toponyms, not only for avoiding noises but also providing them information of area candidates to where they may belong. Most of previous toponym resolution methods were targeting disambiguation among area candidates, which is caused by the multiple existence of a toponym. These approaches were mostly based on gazetteers and contexts. When it comes to the documents which may contain toponyms worldwide, like newspaper articles, toponym resolution is not just an ambiguity resolution, but an area candidate selection from all the areas on Earth. Thus we propose an automatic toponym resolution method which enables to identify its area candidates based only on their surface statistics, in place of dictionary-lookup approaches. Our method combines two modules, area candidate reduction and area candidate examination which uses block-unit data, to obtain high accuracy without reducing recall rate. Our empirical result showed 85.54% precision rate, 91.92% recall rate and .89 F-measure value on average. This method is a flexible and robust approach for toponym resolution targeting unrestricted number of areas.