graphmatcher.java

Jena推理机

        }
        return smallB;
    }
    private Bucket matchBucket(Bucket key) {
        check(HASH_OK);
        Integer hash = new Integer(key.aMember().myHash);
        Bucket rslt = (Bucket)table.get(hash);
        if ( rslt != null ) {
            if ( key.size() != rslt.size() )
                return null;
        }
        return rslt;
    }
    
    
    /* rehash performance notes:
     *Uncommenting below gives an easy way of measuring
     *rehash performance.
     *On a 480ms job the rehash appeared to take over 200ms.
     *(Since with the code below uncommented the same 
     *problem took about 1300ms).
     *
     */
    private int rehash(int lvl) {
        /*
        rehash0(lvl);
        rehash0(lvl);
        rehash0(lvl);
        rehash0(lvl);
         **/
        return rehash0(lvl);
    }
        
    private int rehash0( int level ) {
        in(REHASHING);
        this.table = CollectionFactory.createHashedMap();
        // Set a global to define the hash of an AnonResource
        // level = 0 ==> AnonResource.myHashCode() = 0
        // level = n+1 ==> AnonResource.myHashCode() = hash[n]
        myHashLevel = level;
        
        // Now compute all hashes and stick things in the
        // right buckets.
        Iterator anons = unboundAnonResources.iterator();
        while ( anons.hasNext() ) {
            AnonResource a = (AnonResource)anons.next();
            Integer hash = new Integer( a.myHashCode() );
            Bucket bkt = (Bucket)table.get(hash);
            if ( bkt == null ) {
                bkt = new Bucket();
                table.put(hash,bkt);
            }
            bkt.add(a);
        }
        
        // Produce a checksum for the table.
        int rslt = 0;
        Iterator tit = table.entrySet().iterator();
        
        while ( tit.hasNext() ) {
            Map.Entry pair = (Map.Entry)tit.next();
            int hash = ((Integer)pair.getKey()).intValue();
            Bucket bkt = (Bucket)pair.getValue();
            int sz = bkt.size();
            rslt += sz*0x10001 ^ hash;
        }
        
        in(HASH_OK);
        return rslt;
        
    }
    
    /* subjects identified by bits 0 and 1,
     * predicate           by bits 2 and 3,
     * object              by      4 and 5
     * If neither bit set then role is bound.
     * If lower bit is set then role is unbound to
     * singleton variable in triple.
     * If higher bit is set then role is unbound
     * with anonymous variable that is also
     * unbound to a different role.
     * It is an error if both bits are set.
     *
     *
     * These funny things are read like this: e.g.
     *
     * SXPYOX - the subject is a variable X,
     *          the predicate is another var Y
     *          the object is the same var X
     *
     */
    static final private int NOVARS = 0;
    static final private int SX = 1;
    static final private int PX = 4;
    static final private int OX = 16;
    // SD, PD and OD are illegal values
    // by themselves, should only
    // be found in combination with
    // each other.
    // D for duplicate.
    static final private int SD = 2;
    static final private int PD = 8;
    static final private int OD = 32;
    static final private int SXPY = SX|PX;
    static final private int SXOY = SX|OX;
    static final private int PXOY = PX|OX;
    static final private int SXPYOZ = SX|PX|OX;
    static final private int SXPX = SD|PD;
    static final private int SXOX = SD|OD;
    static final private int PXOX = PD|OD;
    static final private int SXPXOY = SD|PD|OX;
    static final private int SXPYOX = SD|OD|PX;
    static final private int SXPYOY = SX|PD|OD;
    static final private int SXPXOX = SD|PD|OD;
    static final private int S = SX|SD;
    static final private int P = PX|PD;
    static final private int O = OX|OD;
    
    static private boolean legalPattern(int mask) {
        switch (mask) {
            case NOVARS:
            case SX:
            case OX:
            case PX:
            case SXPY:
            case SXOY:
            case PXOY:
            case SXPYOZ:
            case SXPX:
            case SXOX:
            case PXOX:
            case SXPXOY:
            case SXPYOX:
            case SXPYOY:
            case SXPXOX:
                return true;
                default:
                    return false;
        }
    }
    // if i = 0 return the X component of pattern
    // if i = 1 return the Y component of pattern
    // if i = 2 return the Z component of pattern
    static private int varPosInPattern(int i,int pattern) {
        switch (pattern) {
            case NOVARS:
                break;
            case SX:
                if (i==0) return SX;
                break;
            case OX:
                if (i==0) return OX;
                break;
            case PX:
                if (i==0) return PX;
                break;
            case SXPY:
                switch (i) {
                    case 0:
                        return SX;
                    case 1:
                        return PX;
                }
                break;
            case SXOY:
                switch (i) {
                    case 0:
                        return SX;
                    case 1:
                        return OX;
                }
                break;
            case PXOY:
                switch (i) {
                    case 0:
                        return PX;
                    case 1:
                        return OX;
                }
                break;
            case SXPYOZ:
                switch (i) {
                    case 0:
                        return SX;
                    case 1:
                        return PX;
                    case 2:
                        return OX;
                }
                break;
            case SXPX:
                if (i==0) return SXPX;
                break;
            case SXOX:
                if (i==0) return SXOX;
                break;
            case PXOX:
                if (i==0) return PXOX;
                break;
            case SXPXOY:
                switch (i) {
                    case 0:
                        return SXPX;
                    case 1:
                        return OX;
                }
                break;
            case SXPYOX:
                switch (i) {
                    case 0:
                        return SXOX;
                    case 1:
                        return PX;
                }
                break;
            case SXPYOY:
                switch (i) {
                    case 0:
                        return SX;
                    case 1:
                        return PXOX;
                }
                break;
            case SXPXOX:
                if (i==0) return SXPXOX;
                break;
        }
        System.out.println("Bad: " + i + " " + pattern);
        impossible();
        return 0;
    }
    static private interface SomeResource {
        int myHashCodeFromStatement();
        boolean mightBeEqual(SomeResource r);
    }
    static private class FixedResource implements SomeResource {
        int hash;
        Node node;
        public String toString() {
            return "f" + hash;
        }
        public int myHashCodeFromStatement() {
            return hash;
        }
        FixedResource(Node n) {
            hash = n.hashCode();
            node = n;
        }
        public boolean mightBeEqual(SomeResource r) {
            if (r!=null && (r instanceof FixedResource)) {
                FixedResource f = (FixedResource)r;
                return hash == f.hash && node.equals(f.node);
            } else {
                return false;
            }
        }
    }
    
    // Record the occurence of variable r in bag.
    static void count(Map bag, SomeResource r,int pos) {
        if ( r instanceof AnonResource ) {
            int v[] = (int[])bag.get(r);
            if (v==null) {
                v=new int[]{-1,-1,-1};
                bag.put(r,v);
            }
            for (int i=0;i<3;i++)
                if ( v[i] == -1 ) {
                    v[i] = pos;
                    return;
                }
        }
    }
    private class AnonStatement {
        int varCount;
        AnonResource vars[];
        SomeResource subj;
        SomeResource pred;
        SomeResource obj;
        int pattern;
        AnonStatement(Triple s) {
            Map bag = CollectionFactory.createHashedMap();
            pattern = NOVARS;
            subj = convert(s.getSubject());
            pred = convert(s.getPredicate());
            obj = convert(s.getObject());
            count(bag,subj,0);
            count(bag,pred,2);
            count(bag,obj,4);
            varCount = bag.size();
            vars = new AnonResource[varCount];
            add(subj);
            add(pred);
            add(obj);
            Iterator it = bag.values().iterator();
            while ( it.hasNext() ) {
                int v[] = (int[])it.next();
                int last = 2;
                int p;
                while ( v[last]== -1)
                    last--;
                if ( last == 0 )
                    p = SX;
                else
                    p = SD;
                for (int i=0;i<=last;i++)
                    pattern |= p<<v[i];
            }
            if (!legalPattern(pattern)) {
                System.out.println("s: " + subj + " p: " + pred + " o: " + obj + " pattern: " + pattern);
                impossible();
            }
        }
        private void add(SomeResource r) {
            if ( r instanceof AnonResource ) {
                for (int i=0;i<vars.length; i++)