正则表达式避免了Java中不必要的回溯

您好,我是 Regex世界的新手.我想在 Java中的测试字符串中提取时间戳,位置和“id_str”字段.

20110302140010915|{"user":{"is_translator":false,"show_all_inline_media":false,"following":null,"geo_enabled":true,"profile_background_image_url":"http:\/\/a3.twimg.com\/a\/1298918947\/images\/themes\/theme1\/bg.png","listed_count":0,"favourites_count":2,"verified":false,"time_zone":"Mountain Time (US & Canada)","profile_text_color":"333333","contributors_enabled":false,"statuses_count":152,"profile_sidebar_fill_color":"DDEEF6","id_str":"207356721","profile_background_tile":false,"friends_count":14,"followers_count":13,"created_at":"Mon Oct 25 04:05:43 +0000 2010","description":null,"profile_link_color":"0084B4","location":"WaKeeney, KS","profile_sidebar_border_color":"C0DEED",

我试过这个

(\d*).*?"id_str":"(\d*)",.*"location":"([^"]*)"

如果我使用惰性量词,它有很多回溯.*? (regexbuddy中的3000步),但锚“id_str”和“location”之间的字符数并不总是相同.此外,如果在字符串中找不到位置,则可能是灾难性的.

我怎么能避免
1)不必要的回溯?

2)更快找到不匹配的字符串?

谢谢.

您可以尝试这样做:

(\d*+)(?>[^"]++|"(?!id_str":))+"id_str":"(\d*+)",(?>[^"]++|"(?!location":))+"location":"([^"]*+)"

这里的想法是尽可能地使用具有受限字符类的possessive quantifiersatomic groups来消除回溯(就像你在上一个捕获组中所做的那样)

例如,为了避免第一个惰性量词,我用这个:

(?>[^"]++|"(?!id_str":))+

正则表达式引擎将尽可能多地采用非双引号的所有字符(并且没有注册单个回溯位置,因为使用了占有量词),当发现双引号时,前瞻检查是否没有后跟anchor id_str“:.所有这部分都被原子组包裹(内部没有回溯)重复一次或多次.

不要害怕使用前瞻内部会很快失败并且只有在找到双引号时才会感到害怕.但是你可以尝试使用相同的i,如果你确定它不如“(或者如果你发现之前的罕见字符)那么频繁:

(?>[^i]++|i(?!d_str":))+id_str":(...

编辑:这里的最佳选择似乎是,不那么频繁:( 200步与422双引号)

(\d*+)(?>[^,]++|,(?!"id_str":))+,"id_str":"(\d*+)",(?>[^,]++|,(?!"location":))+,"location":"([^"]*+)"

要获得更好的性能,如果有可能,请尝试在模式中添加锚点(^),如果它是字符串或换行符的开头(使用多行模式).

^(\d*+)(?>[^"]++|"(?!id_str":))+"id_str":"(\d*+)",(?>[^"]++|"(?!location":))+"location":"([^"]*+)"
相关文章
相关标签/搜索