基于BitSet的广告索引检索引擎实现

 

 编写不易，转载请注明 （http://shihlei.iteye.com/blog/2358063）

 

一 概述

广告系统中，广告活动创建时，运营人员通常会根据广告的受众情况，设置广告的基本定向，如香奈儿推广 需要投放上海的女士用户。

 

因此，根据定象条件对广告活动进行索引和检索是投放引擎的必备功能。

 

通常实现可以使用ElasticSearch这样的索引引擎。本文尝试实现一个简单的基于BitMap的内存索引和检索引擎。       

 

二 思路

索引：为每个定向条件构建一个BitSet，在该定向条件创建索引，相当于将BitSet 的 广告活动ID位 置1；

检索：提供定向集合，取出指定定向的BitSet，BitSet之间通过“与”运算，取交集获得最终的BitSet，获取最终BitSet中位为1 的下标即满足条件的bitmap。

 

优点：内存索引且内存空间很小。

缺点：

1）当BitSet位数很大时，进行&运算会比较慢，待进一步研究。

2）广告活动ID 必须为 整型。

3）定向条件很多的情况，感觉使用还是有些困难。

4）定向条件之间会有“或”运算的情况，这里没有考虑。

        其他没有深想。

 

三 实现

public class AdvEngine {

    private static final int BITSET_SIZE = 100000000;

    //索引列表
    private Map<TargetEnum, BitSet> indexes = new HashMap<>();


    public static void main(String[] args) {
        AdvEngine advEngine = new AdvEngine();

        //广告1000 投放：北京，女
        advEngine.index(1000, Arrays.asList(TargetEnum.GENDER_FEMALE, TargetEnum.AREA_BEIJING));
        //广告2000 投放：上海，女
        advEngine.index(2000, Arrays.asList(TargetEnum.GENDER_FEMALE, TargetEnum.AREA_SHAGNHAI));
        //广告3000 投放：女
        advEngine.index(3000, Arrays.asList(TargetEnum.GENDER_FEMALE));
        //广告4000 投放：上海 ，男
        advEngine.index(4000, Arrays.asList(TargetEnum.GENDER_MALE, TargetEnum.AREA_SHAGNHAI));

        System.out.println("上海,女 可投放广告：");
        List<Integer> campaingIds = advEngine.search(Arrays.asList(TargetEnum.GENDER_FEMALE, TargetEnum.AREA_SHAGNHAI));
        campaingIds.stream().forEach(System.out::println);

        System.out.println("女 可投放广告：");
        campaingIds = advEngine.search(Arrays.asList(TargetEnum.GENDER_FEMALE));
        campaingIds.stream().forEach(System.out::println);
    }


    /**
     * 创建索引
     *
     * @param campaignId 广告id
     * @param targets    定向类型
     */
    public void index(int campaignId, List<TargetEnum> targets) {
        for (TargetEnum target : targets) {
            BitSet bitSet = indexes.get(target);
            if (bitSet == null) {
                bitSet = new BitSet(BITSET_SIZE);
                indexes.put(target, bitSet);
            }
            bitSet.set(campaignId, true);
        }
    }


    /**
     * 查找符合类型的广告活动
     *
     * @param targets 定向类型
     */
    public List<Integer> search(List<TargetEnum> targets) {
        List<Integer> campaignIds = new LinkedList<>();
        if (targets.isEmpty()) {
            return campaignIds;
        }

        BitSet finalSet = null;

        //取出满足所有定向条件的集合
        long start = System.nanoTime();
        for (TargetEnum target : targets) {
            BitSet campaingBitSet = indexes.get(target);
            if (campaingBitSet == null) {
                break;
            }
            if (finalSet == null) {
                finalSet = (BitSet) campaingBitSet.clone();
            } else {
                finalSet.and(campaingBitSet);
            }
        }
        long end = System.nanoTime();
        System.out.println("time1 : " + (end - start));
        if (finalSet == null) {
            return campaignIds;
        }

        long start2 = System.nanoTime();
        for (int i = 0; i < finalSet.length(); i++) {
            if (!finalSet.get(i)) {
                continue;
            }
            campaignIds.add(i);
        }
        long end2 = System.nanoTime();
        System.out.println("time2 : " + (end2-start2));

        return campaignIds;
    }

    /**
     * 删除索引
     *
     * @param campaingId 广告ID
     */
    public void dropIndex(int campaingId) {
        //取出满足所有定向条件的集合
        for (BitSet campaingBitSet : indexes.values()) {
            campaingBitSet.clear(campaingId);
        }
    }


    /**
     * 定向类型枚举
     */
    public static enum TargetEnum {
        //性别定向
        GENDER_MALE,
        GENDER_FEMALE,
        //地域定向
        AREA_BEIJING,
        AREA_SHAGNHAI;
    }

}

 

四 BitSet说明

（1）设置位

void set(int bitIndex)

 

（2）获取位

boolean get(int bitIndex)

 

（3）操作

void and(BitSet set) //与

void or(BitSet set)  //或

void xor(BitSet set) //异或

 

（4）清除位

void clear(int bitIndex)

评论

4 楼 ShihLei 2017-04-24  

wsnbmw 写道

改为if (campaingBitSet == null) {
finalSet=null;
break;
}

是，不满某个定向条件，直接退出

3 楼 wsnbmw 2017-04-19  

改为if (campaingBitSet == null) {
finalSet=null;
break;
}

2 楼 wsnbmw 2017-04-19  

if (campaingBitSet == null) {
finalSet=null;
continue;
}

1 楼 wsnbmw 2017-04-19  

    List<Integer> campaingIds = advEngine.search(Arrays.asList(TargetEnum.GENDER_FEMALE, TargetEnum.AREA_SHAGNHAI)); 如果换成其它城市就有bug，无法使用